First (and last?) problem solving episode

so school is about to end in less than 2 weeks, yay, at the same time test 3 is next week, followed by the exam itself the next next week, and i have to write a problem solving episode to at least get full credits for this, booo. now all ranting aside,

i suppose i'll prove ∀ n ∈ ℕ, Me > n. haha now all jokes aside, i guess i'll do this episode on problem set #3. So using Polya's steps, i have to make a conjecture about a closed form for G(n) and prove my conjecture given that

∀ n ∈ ℕ, G(n) = { 1, if n = 0 and 3G(n-1) + 1, if n > 0

Step 1: Understand the problem
So here we have to find a close form for G(n), make a statement for our claim, and then prove the claim.

Step 2: Devising a plan.
1) we will have to unwind G(n) and see how the values may have a pattern. so set n as a not too small, but not too large number, and we find the value for G(n) for each n.
2) Given we have found a pattern for the values, we will have to rewrite it in the closed form of G(n).
3) now with the closed form we will actually prove the closed form is correct. Given the closed form does not rely on previous values of G, simple induction should suffice.

Step 3: Carry out the plan
1) so we unwind G(n) now say when n = 5, so
G(0) = 1
G(1) = 3G(0) + 1 = 3(1) + 1 = 4
G(2) = 3G(1) + 1 = 3(4) + 1 = 13
G(3) = 3G(2) + 1 = 3(13) + 1 = 40
G(4) = 3G(3) + 1 = 3(40) + 1 = 121
G(5) = 3G(4) + 1 = 3(121) + 1 = 364

2) looking at this, we see a pattern where to find G(n+1) we add 3^n+1 to G(n), so we can say G(n) = \sum i=0 to n, 3^i, but since we need a closed form expression, thus we must rewrite the equation in another way.

From above we know G(n+1) = G(n) + 3^(n+1), and from the definition of G(n), we know G(n+1) = 3G(n) + 1, thus equation both expressions we get
G(n) + 3^(n+1) = 3G(n) + 1
3 G(n) - G(n) = 3^(n+1) - 1
G(n) (2) = 3^(n+1) - 1
G(n) = 3^(n+1)-1 / 2

3) so now proving this using simple induction, as always we start with a claim.

Claim: P(n) : ∀ n ∈ ℕ, G(n) = 3^(n+1)-1 / 2

Then we start with the base case.

Base Case: n = 0, G(0) = 3^(0+1) - 1 / 2 = 3 - 1 / 2 = 2 / 2 = 1, so P(0) is true.

Then we will state our induction hypothesis and induction step.
Induction Step:
Assume n is an arbitrary number, and that P(n) is true, i will prove that P(n) => P(n+1).

G(n+1) = 3G(n) + 1
= 3(3^(n+1)-1 / 2 ) + 1 // by IH
= 3(3^(n+1)-1/2) + 1
= 3^(n+2) - 1 / 2
= 3^((n+1)+1) - 1 /2 as required

∀ n ∈ ℕ, P(n) => P(n+1)

Step 4. Looking Back

then we have proven the close form of G(n) so we can conclude that ∀ n ∈ ℕ, P(n) is true.

Assignment 3

so our group started assignment 3 a while ago, looking at it, it was relatively easy to do. This seems easier than the past 2 assignments, question 1 was about loop termination, and loop invariants, it was a easy question as we've done it on test 2, and proving IH ^ precondition => post condition is easy.

Question 2 was about proving a Regular Expression denotes L, this was easy since there was an example in the lecture on how to prove it, we have to prove L is a subset of the RE, and the RE is a subset of L, otherwise RE does not denote L. although it is a bit messy with some of the parts since there's kleene stars everywhere, but i got through that question easily.

Question 3 was about proving that any regular expression that doesn't include a Kleene star denotes a finite language. we have a general idea on how to prove this, just need to write it down in complete sentences, we will be using the inductive definition of RE, and proving it by excluding the Kleene star, so all the languages even by concatentation should be finite.

Question 4 deals with DFSA and the carteisan product technique, and state invariants, our group have already derived the machine for that question, just takes a long time to write down all the states for the machine in words as opposed to a diagram.

i guess i will be doing my first problem solving episode huh since school's almost ending, 1 more week!! :D:D

A2 Handbacks, Test 2 and RegExp

Assignment 2 were marked and marks were handed back today, haha i was surprised when i first saw my mark, i thought i did a lot worse. But i suppose i did ok now

Test 2 is coming up this week, i think i won't have a problem with it since i pretty much know what i did for assignment 2 and the problem set 4, the only thing i might have to review is the master theorem and try to absorb what it is all about.

We did regular expressions this week, reg exp is ok for me since i know how to write and use them in programming, the only think awkward is the new symbols like + for ors(since + means 1 or more occurences in programming), and multiply to concatinate strings together, it is also awkward because now we try to prove some regular expressions, though i feel that i understand what is being said in lecture., so i guess it'll be pretty alright.

speaking of which i still have to write some problem solving episodes for this slog.

Program Correctness and induction

Program correctness sounds fun, given a precondition and post condition, you try to hack your way to break the program, what makes a program correct? or it works?, personally, i think when some one says "yay it worked" means given a correct input, it spits out the correct output, but i personally don't believe programs to "work" 100% correctly, but hey only precondition and post conditions needs to be satisfied ;)

even if i code a program, i don't think it'll work 100% correct, i'm sure someone will be able to hack or break apart my program, but hey, if it satisfies what the assignment was required, why do extra work? (and i'm lazy to find all cases, but i do have to do that for 207 otherwise i won't be having a good mark for test cases! ;( ) (speaking of hacking, that reminds me of the movie "Live Free or Die Hard" hehe where hackers were able to hack into FBI network(talk about something important as that..) or the national database.. (i sure hope it doesn't happen here! or there goes all my money)

the last couple of lectures certainly improved my understanding of induction, not just the simple "you have T(n) and prove T(n+1) thing", but allowed me to understand that we make a claim, assume something, then using that hypothesis, prove what we want to prove, which is not limited to just the "n+1" case, such as proving T(n) >= logn or G(n) <= F(n) as the question in the assignment.

o well now that i have the assignment and problem set out of the way, onward to study for midterms and finish other assignments :(

Problem set 4 and Assignment 2

with most of the midterms and assingment out of the way, i finally had a time to sit down and look at the problem set 4 and assignment 2 which is due next monday

looking at problem set 4, i think i can breeze through it with ease since it was a prove by induction that precondition => postcondition (if its true), which is almost the same thing as what we did today in class

looking at assignment 2, it feels pretty alright, #2 is about finding close form and proving it, i already found some kind of pattern for it, now i have to just put it down on paper and prove it.

#3 shouldn't be too bad either, although i do have to find a algorithm to generate the "steps" and then just have to prove that G(n) is less or equal to the fibonacci numbers

#4 is about the same as the problem set 4, proving precondition implies postcondition, the only thing i have to refresh on for #4 is the thing about run-time and a bound for it, but i think we have already done something similar in class with the time complexity of mergesort which is nlogn (i think it was mergesort)

only thing i have a problem is question 1, i forgot what ternary trees are, so i will have to refresh my memory on that.

overall i hope i can finish this by the weekend so i can work on my other assignments and study for 2 of my midterms :)

Problem Set 3

So after reading problem set 3, and writing a lot of draft work and equating equations together, i finally came up with the closed-form for G(n), although certainly not something like we've done in class, but it certainly only requires a value n, and nothing else to solve for G(n) and satisfy closed-form expressions, and it works, now that is left for me to do, is write out the proof.

Term Test #1

i find Term Test #1 to be fair, i knew the answers to all the questions unfortunately, in the 50 mins period span, i managed to only write a structure and a few of the cases for #3 (which was the subset question) without finish proofing it.

Question 1 was pretty straight forward, using simple induction and proof 3^n > n^3 + 10, basically it was algebra and inequality manipulation, going from 3^(n+1) to showing its greater than (n+1)^3 + 10.

In Question 2, although some people i talked to used complete induction, i just used simple, it was like the sum of the fib numbers, we just need to proof that f(n) > 2n, with this, i first say f(n+1) = f(n-1) + f(n), then by using the def of f(n) i rearranged so that f(n-1) = f(n) - f(n-2), such that its 2f(n) - f(n-2), and then everything works itself from there using the I.H. With a bit manipulation we arrive to 2(n+1) which is what we wanted.

In question 3, it was number of subsets such that its 3*2^n-2 if 1 or 2 or both are omitted. It was a fairly simple proof using cases, split it into 1 being omitted, 2 being omitted, then both elements being omitted, and soon enough adding them up, and taking away elements that were repeated(such as empty case), we would be able to arrive at our conclusion. Unfortunately i spent some time thinking about the inequalities manipulation in question 1, and thus not had time to finish question3, however i did put a conclusion in even though i did not finish the proof, as i see the marking scheme from the past term test that marks were taken off if certain things were omitted. funny how i mention omitted things and question 3 has the omit elements.

maybe i can proof using induction my test mark if the n required things were omitted eh?

Recursion

One of the things i love the most, short and simple. Looking at the lectures done the past week about recursive functions and how to prove them by induction seems the same, most of the time you might need more than one base case(fibonacci numbers), some times you only need one! like the function we did in class(the sum of the fibonacci numbers).

looking past that, we also try to do recursive functions in code, i personally don't know python, and am more familiar with java and the other programming languages, but using recursion in code is pretty neat, although, not every requires recursion as it does take up quite a heap of memory space, going forward once then backwards to output the answer. Recursion quite easy and simple, define a basecase, then for the rest, just call the same function again. Good use to loop through binary trees or even directories on the computer!

We also did some unwinding, calculating the time it takes to loop through the recursive function (in quite a lazy way i must add! but hey we are lazy :-) ) doing some unwinding certainly have to be careful and not forget about adding time it took previously,

looks like term test 1 is coming up this friday, i don't think it'll be too brutal considering most of the things is about induction and the principle of well ordering, which shouldn't be too brutal, as i only had some problems with A1 #2 (although i do admit after seeing the solution for it, we were thinking too complicated....)

Assignment 1

finally had a chance to look at this last night, question one was a breeze as it was something i already knew or may have even proven before, then looking a question 3 after looking up what the heck golden ratio actually is, and from questions / hints provided in the question, i think i have an idea on how to use that to prove root(5) is irrational

time to go to school! woo :D

Week 2

The second week of school has passed. We were still doing induction, but this past week we worked at strong inductions. Strong induction we learn this year is different than what i've learned in the past, in the past, all we learned was more like proving something similar to fibonacci numbers, now, i will need more explanation in how i derive the proof and the n+1 cases

i'm glad problem set 1 is out of the way, i read problem set #2 and similarly what we did in class, so i think i'll start working on that tomorrow, then after i can finally start working on A1 now that most work are out of the way.

First Week of CSC236

After a long and fun summer, school resumed again, time flew by quick and soon the first week of school is over.

First week we learned about induction, concepts were fairly easy as i had done inductions in high school as well as in mat137.  However, the ways of the write up were a bit different as we did not had to deal with predicates, and we only had to prove left = right side, but now there is a few more explanations to do instead of just a few lines of algebra.

i like Danny's new way of teaching by using his tablet and the projector. The new contrast of black and neon green reduces the con of reflections by the light on the blackboards causing some of the things he writes unclear or fuzzy.  And now he wouldn't need to erase the board and just add a new page when his page becomes full :)

This has been a while (or maybe a few years) since i've ever wrote a blog, mostly because i am too lazy and maybe i just like to remember things in my head.  I don't think i'll have a lot to say this week as nothing much went on this week as it's the first week of class, (not much hw, etc), maybe i'll have more things to write next week as the weeks get busier and things i learn grows.

All i can probably say now is onto problem set 1 and assignment 1 haha and a very very busy upcoming year :D

Test

test how this works