Week Five

Monday,
---------- Oct. 6, 2008
Today, we talked about the closed form of recurrence. We started with Fibonacci Sequence. Although the formula seemed so strange, Professor Danny explained that it is very necessary. Writing a recursive code for F(n) is not something wise especially if n is greater than 25. I remember professor Paul Gries doing this example in CSC148 last year. When he called F(30), a continuous flow of integers kept appearing on the screen, just like a matrix. It was cool, but it taught me that even nice useful things like Fibonacci sequence can be lethal.
Moreover, using while loops instead of the closed form is not a good option if n is larger, because F(n) is a linear function and you have to keep adding till you reach that larger n.
The second example we did was H(n) and we used a similar approach to find the closed form.
Finally, we talked about defining sets with induction. The example about proving that the number of nodes in a binary tree is less than or equal to 2^(H(T) +1) - 1 was really easy but I did not get the part that defining a property can be derived from the definition itself.

Wednesday,
---------- Oct. 8, 2008
We continued with defining sets with induction and the example of the binary tree. We did a second example about matching parentheses, it is easy but I am so confused. What I did to prove that P("(s1)") holds was just proving that 1+L(s1) >= 1 + R(s1). It is pretty simple and straightforward. According to professor Danny's solution, we need to consider s^ = s^^ * s^^^ where s^ is a prefix of s1, s^^ is a prefix of "(" and s^^^ is a prefix of s^^. Then by induction hypothesis, L(s^) >= L(s^^) +L(s^^)>= R(s^^) + R(s^^).
I do not really get it; why should we break them like that? I guess I have to take another look at the lecture slides and the course notes.
Another thing that is bugging me is that it has been more than 24 hours since A1 marks have been posted, and I still did not get my mark. I cannot use the online marking tool because my partner was the one who submitted the assignment. I cannot use cdf/students because the marks are not up on cdf students either, and my partner did not email me with the mark :(

Friday,
---------- Oct. 10, 2008
We had our first test today. I did not find a problem in studying induction because the examples in the lecture slides and course notes were thorough and easy to follow. However, it was not until 8:30 pm when I discovered that materials from chapter 3 will be on the test as well. I did not know where to stop; so I studied everything even Monday's and Wednesday's lectures and I went to the test praying that nothing outside induction will show on the test.
The test was neither easy nor hard, but I spent the whole 50 minutes writing. For question 2, we had to find a number k such that \forall n>k, 3^n <>