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.