Grand Finale?

Since this is the last post, I guess this should be a review of CSC236. Compared to other courses, I think this was that one course that at first when some topic is taught in lecture, I think I had no understanding of the material, but I when I actually do a problem related to it, all the things mentioned in lecture, made perfect sense! I think the tutorials and the daily quizzes helped too. A lot.

Anyways, the slog handout says that I should mention the problems or difficulties we faced through out the course in each post and how I planned to over come it. Well, when I wrote previous posts, I don't think there was a "difficulty" in the material. But having said that, I did have difficulties when trying to solve problems.
Personally,  I think the best way to actually understand something that is difficult is to follow through it with a good example. For each step taken in the example, the first thing to do is to understand why it is done. Then we should relate to our own question and see how that reason and the step could be applied to get the required result. This is actually very different from looking at the example and trying to do the exact step that it takes on our own problem because 1, we will never learn anything and 2, if a problem comes up later in the question that is not in the example, we will have no idea how to get through it because we didn't know what we did in the beginning. I guess this is a general comment about how I dealt with difficulties in the course.

Danny Heap and the TAs were really good in making us understanding the material. They were also a great help during office hours!

Farewell!
(last minute posting, again!)

Well Ordering

Week 3 : Well ordering

To me, this is a topic that was not really clear for me. I did not understand why this was distinctly recognized from all the other proofs because it basically followed the steps that mathematical induction took. But, after some readings, I realize that proof by well ordering uses the fact that there is a smallest element in a set (I know this was already said in lecture, but I did not understand the significance!). Most of the time, we are trying to prove that there is no value for which a predicate is false, by using the principle of well ordering. 

I found an exam question related to this topic on the December 2009 examination.

Use the principle of well ordering to write a proof that for all n ≥ 1,

This statement will be proved by Contradiction. 

Let P(n) be: For all natural numbers n ≥ 1, the above statement is True

Assume that P(n) is false for at least one positive integer in n. Let S be the set of all possible integers for which P(n) is false. Using these two assumptions we can come to the conclusion that s is non empty and by the Well ordering principle S must contain a smallest element. Suppose that k is the smallest element:

=> We know that k cannot be 1 since for n=1, P(1) is true. 

=> Therefore, k > 1. This also implies that k-1 > 0. Since k -1  ≥ 1, and k is the smallest value for which P(n) is true, we can assume that 

=> Then P(k-1) is true since Since k -1  ≥ 1, k is the smallest value for which P(n) is false and k -1 < k

=> Therefore:

Knowing what P(n-1) is, now, we will compute P(k) :

=> CONTRADICTION! 

=> The last statement contradicts our assumption that k is the smallest value for which P(n) is not true since we proved that if P(n-1) is true, then P(k) is true as well. 

=> So, a smallest value k does not exist in set S and S is empty.

Therefore, there are no values bigger than 1 for which P(n) is not true. 

Since P(1) is true, then the statement that for all natural numbers n ≥ 1

Unwinding…

Finding the closed form

A problem that I found on the 2011 Fall Term Exam

Given the recurrence T(n) =  7T(n/3) + n ,  with the initial condition T(1) =  1. Assume that n is  a  power of the appropriate integer. Either by iterating the recurrence or by drawing a recursion tree with all details  as  presented in the notes, find  an exact closed-form solution.

We will solve by  iterating the recurrence(unwinding).  

The problem tells us to assume that n is a power of the appropriate integer. In this case it will be 3. The reason that we do this is to make sure that when n is divided by 3 to get T(n/3), we will know that the recursion will be of the right value and not a decimal rounded up or down which would make it harder for us to come to conclusions.

So assume that n = 3^a

So now we start unwinding…

T(n) =  7 T( n/3 ) + n                                                # i = 1

T(n) = 7 ( 7 T( n/9 ) + n/3 ) + n    

T(n) = 49 T( n/9 ) + 7n/3 + n                                    # i = 2

T(n) = 49 ( 7 T( n/27 ) + n/9) + 7n/3 + n 

T(n) = 343 T( n/27 ) + 49n/9 + 7n/3 + n                   # i = 3

T(n) = 343 ( 7 T( n/81 ) + n/27 ) + 49n/9  + 7n/3 + n

T(n) = 2611 T( n/81 ) +343n/27 + 49n/9 + 7n/3 + n  # i = 4

.

. The key point is to figure out what each recursion step would be in terms of i.

.

T(n) = 7ⁱ T( n/3ⁱ ) + 7^i-1n/3^i-1 + 7^i-2n/3^i-2 + … + 7⁰n/3⁰

T(n) = 7ⁱ T (n/3ⁱ ) + Σ(from k=0 to k = a – 1) (7/3)^kn

So, All the recursions would stop at T(1) since that was the only value that we were given that would give an answer without any recursion. In this case,  there will be no recursions when T(n/3ⁱ) = T(1)

     ð n/3ⁱ = 1

     ð n = 3ⁱ

     ð i = log₃ n

     ð i = log₃ 3^a

     ð i = a

Therefore, in the very last iteration, we could substitute i = a:

T(n) = 7^a T(1) +  n Σ(from k=0 to k = a – 1) (7/3)^kn

T(n) = 7^a + n (( 7/3 )^a – 1) / (( 7/3 ) – 1)

Therefore the closed form in terms of n would be: 

T(n) = 7^log(3) n + n (1 -(7/3)^log(3) n) / (1 -(7/3))

Complete induction

Week 2 : Complete induction.

Complete induction is mostly required in solving problems with questions that require us to combine smaller elements such as binary trees.

P(n) : Every rectangular array of chocolate m*n squares can be broken up in mn – 1 tries.

For a rectangular array to exist, the dimensions must be bigger than zero. Therefore, the predicate implies that we only have to prove it in the set of positive natural numbers in terms of either m or n.

For complete induction, we always work under the assumption that for all natural numbers i, if i is strictly smaller than n, then P(i) is true.

Then we prove the most basic case in the set of natural numbers which is n= 1
Therefore, if there is a rectangular array of m*1 squares, then to break it up in to 1*1 pieces, we will have to break it m-1 times because all m number of chocolate pieces are joined in a straight line and to break them in to single pieces, there is m-1 joints to separate.

Next in the inductive step, we consider arrays where n > 1
         An array of size m*n can be made by joining an array of m*1 and m*(n-1). Since we assumed that for all i<n, P(i) is true, then the array of m*1 requires (m-1) breaks to separate in to single pieces while the array of size m*(n-1) requires [m(n-1)-1] tries. When these two are combined, that requires one more break in the resulting array of size m*n to be broken off in to single pieces.
So, the array m*n will in total require (m-1) + (m(n-1)-1) + 1 number of breaks which equals (mn -1).
         Thus, for an array of size m*n, mn-1 tries are required to be broken up in to single pieces.
         Therefore, P(n) is true if n > 1

We proved that the predicate is true for both the conditions. So now, the results can be extended to the conclusion that every rectangular array of chocolate m*n squares can be broken up in mn – 1 tries

Mathematical induction:

Week 1 : Mathematical induction: P(n) => P(n+1) for all natural numbers n

P(n) : ∀ n ∈ ℕ, 7^{n -}1 is a multiple of 6

Method:

First prove base cases.
This is usually P(0) and/or other cases that we cannot prove by assuming the case before it is true. For example, we can’t assume P(-1) is true to prove P(0) since -1 is not a natural number. In this problem, the only base case we need to prove is when n = 0
So, P(0) = 70 -1 = 0 = 6 * 0
Since the result of P(0) confirms the predicate, then the base case is true

Then comes the inductive step where we assume for an arbitrary natural number n, P(n) is true.
Under this assumption, we write down the elements involved in P(n+1) in terms of that of P(n).

             P(n+1) = 7ⁿ⁺¹ -1 = 7( 7ⁿ ) - 1

Since we know that P(n) is true, that means 7ⁿ = 6k + 1 (#7ⁿ -1 is a multiple of 6)
* We write P(n+1) in terms of P(n) because we know that P(n) is already true through the assumption, which would make it easier for us to see how the relationship between P(n+1) and P(n) will hint that P(n+1) is true as well.

Now, we can substitute 7ⁿ as 6k + 1 to see if the result would still be a multiple of 6 in P(n+1)
P(n+1) = 7ⁿ⁺¹ -1 = 7(6k + 1) -1 = 42k + 6 = 6(7k + 1)

This shows that 7ⁿ +1 -1 is also a multiple of 6 and causing P(n+1) to be True.
Since n was considered to be just an arbitrary natural number in the assumption, we can extend the conclusion to say that for any natural number, if P(n) is true, then P(n+1) is true.
Therefore, for any natural number n, 7ⁿ -1 is a multiple of 6

REVIEW

Phew! That was one hectic week. Unfortunately, like always, I had barely enough time to spend on SLOG posts. AND ITS DUE TONIGHTTT!

I know I haven't been paying much attention to the SLOG entries, but I felt like I should make use of the effort by reviewing the topics that we covered in the beginning of the course like different types of induction. Might as well start studying now without waiting till last minute right... :)

Deterministic and Non-deterministic FSAs

We learned about non-deterministic FSA's last week. I kind of missed the first half of the class so I didn't quite catch what the main difference between NDFSAs and DFSAs is. The lecture slides didn't really point out a specific answer to this either. So I had to ask everyone's best friend, Google.

http://cs.union.edu/~striegnk/courses/nlp-with-prolog/html/node4.html

I understand what is mentioned in the site and it actually relates to the example machine discussed during the lecture. So, according to my understanding, the main difference between the two types is that the NDFSAs can contain two paths for the same input from a single state hence the state being non deterministic?

We also have a3 due this friday! I need to start on it so i won't end up rushing through it on last minute. And hopefully, when i work through the assignment, I would get a better grasp on what the differences between   NDFSAs and DFSAs are.

The Master of all theorems : "The Master Theorem" ?

Clearly, the theorem was given the title for a reason. It was made to make everyone's lives just a little bit easier when finding time complexity of an algorithm without doing all the messy unwinding.. 
I studied it over and over, I knew how to use the Master Theorem, walked in to the write Test 2, saw Master Theorem question.... Perfection! ..or so it thought. What do I end up doing? Unwinding T(n) before applying the Masters Theorem!!!! >.< 
I should just slap my self over and over and over and over again.. and more. *Sigh*

I remembered to write what P(n) this time though! Life lessons I'll say.

So, to make up for my mistake,  Here goes..

The Masters Theorem: 

For T(n) =  aT( ⁿ/_b ) + f(n) 

T(n)  =     Θ (n^d)    if a < b^d

         =     Θ (n^d log n)    if a = b^d

        =     Θ (n^log_b a )      if a > b^d

where a is the number of recursions, b is how many parts we divide n in to  and finally d is the largest degree of the polynomial f(n)

So, if i was given  lets say --- T(n) = T(⌈ⁿ/₂⌉)+ T(⌊ⁿ/₂⌋) +  1

If n was a power of 2,  we can simplify T(n) to be: T(n) = 2T(ⁿ/₂) +  1

Now,  it's visible that a = 2, b = 2 and d = 0 since the largest degree of 1 is 0.
With this information, and the use of the Master Theorem, the complexity time of T(n) would be : 
Θ ( n^log_b a )  since 2 > 2⁰ 

Finally,

T(n) = Θ( n^log_b a )
T(n) = Θ( n^log₂ 2  )  =  Θ( n )

Phew! There, done. 

Last Minute

So we had assignment 2 due yesterday, which I handed in on the last minute. I checked the time, it was 11.58pm. Woo! No pressure. No pressure at all.

So in a2, i understood question 1 after the TA explained how the question should be answered in 3 parts. And i am glad that we didn't have to show proof of how the fibonaaci sequence ended up with the golden ratio which was what i was really confused about. But in question 2, I didn't quite understand how to prove that the function is in Theta of lg(n). What i did was prove that two values, one larger than n, and one lower than n that are powers of 2 to be elements of the Order of lg(n) and Omega of lg(n) respectively using the closed form for T(n). Due to that reason and that fact that T(n) is a non-decreasing function, i reasoned that T(n) is an element of Theta of lg(n).
I don't know to what degree this proof is correct, but it kind of makes sense to me.

Something that I did not understand however was the significance of the Max and the floors and ceilings. Since T(n) is an increasing function, wouldn't the Max always be the ceiling of (n/2)? I did not quite know of how to address that in the assignment. So i'm really looking forward to seeing the answers to this assignment.

Bad Times

I really need to get used to the habit of blogging more often! >.<

GAH.. I couldn't finish the quiz this week. I clearly understood what the TA was talking about when he did the tutorial problem, but I guess I kind of blanked out when I got the quiz.

I don't quite remember what the question was, but I know I failed to make the connection that

T(3^(k+1) / 3) is equal to T(3^k)

And that is just basic math that I failed at too! :(

Hopefully i get 1%? If not, well, at least I will always remember that x^(k+1)/x = x^k. 
...maybe.

MUST. GET. SOME. SLEEP.

It’s around 4am and I'm trying to finish typing up assignment 1. I finished it on paper like an hour ago, but nope, it just wasn't good enough! Typing up everything is very time consuming, I barely finished typing up question 2. At one point I lost track of what I was typing which is why I decided to take a break and do something else useful, like blogging. I procrastinated doing this for like 3 weeks, well its technically 2 or 3 days considering I wasn't aware that the SLOG was due next week until my friends started to talk about it. Yup, shows how much I pay attention. But all is well now :)

So a1, I know we all dreaded this assignment before we even saw it. Maybe I'm speaking for myself here, but it’s not that bad. :/ Question 1 and 2 was basic stuff, lectures and text book gave a sufficient guideline. Question 3, well, my life would have been so much easier if I knew how to prove a bijection. ( :s Haha, even ms word does know the word bijection. It keeps on correcting me to “bisection”) We did simillar problems in CSC165 last semester, so past notes helped.

Question 4, now that's the challenge. For the problem solving part, the instructor’s hint on piazza is helpful. But unfortunately, that's not the main problem in my case. Me, being extremely bad in English, just can’t find the right words to explain the answer.  In my mind, I could explain how it works, but the moment I start to put it in to words, I get lost in my own sentences. This is a case where numbers aren't much of a help either. If it’s not clear to me, I can’t expect the TA to understand all my babbling so I’ll just have to read over more and edit until it makes sense. I just hope I’d be able to get some sleep before classes tomorrow

^^^^ All that was written on Friday morning. But my laziness didn't take the time to make a blogger profile and actually publish the post. And now, I'm too lazy to type up another one. So this will have to do. One day, procrastination will destroy me. Until then, so long... :)