Week Four

Monday,
---------- Sept. 29, 2008
All right, it is recursion time. Dealing with running times of recursive functions is something I was avoiding since last year. Of course, we did not start directly with time complexity or efficiency of recursive codes. Rather, we started with my favorite sequence ever, the Fibonacci Sequence. We used complete induction to prove that the sum of the first n Fibonacci numbers is f(n+2) -1.
I am happy because we did this example because it corrected a misunderstanding I had. Although we are done with the induction chapter, I still instinctively assume P(n-1) then use P(n) to prove P(n+1) in complete induction (I guess I have mis-learned this point in MAT137). So when I did the scratch work and compared it to the professor's solution, I was a bit shocked for the silly mistakes I made because P(n) is not assumed to be true; we have to prove it.


Wednesday,
---------- Oct. 1, 2008
I could not attend today's lecture because I stayed awake working from Tuesday, 10:30 am to Wednesday, 11 am on a project for my architecture course.
I think they talked about something called unwinding, I am not sure. I will have to read the course notes and the lecture slides.


Friday,
---------- Oct. 3, 2008
Unwinding turned out to be really interesting. You start with a recursively defined sequence, then keep applying the definition and recording the number of steps done so far, till you get to n = 0 or 1 or whatever base case you have. Unwinding is used for finding closed form for recursive formulas.