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?