Week 7 - Thursday Oct 23, 2008

Week 7 is gone. Time flies, that's for sure. I survived the worst week of this semester so I am happy about that. 

The deadline of Assignment 2 was approaching and I was glad I solved the ternary trees question a long time ago. It seemed that it was the hardest problem and it took everybody quite some time to figure it out.

In the lecture we saw the correctness of algorithms. We looked at the binary search algorithm and we proved it's correct and we did the same with Euclid's algorithm for the gcd. 

Test 2 is coming up (in about a week) so I need to review the material. 

Week 6 - Thursday Oct 16, 2008

Week 6 is already gone. Time really flies and that's not a bad thing as this week, i.e week 7, I have 4 midterms in three days, I have and three assignments.Too much work!

Anyways, the lecture was shorter this week because the morning section missed the Monday lecture, it was Thanksgiving day. No complaints there, it was nice to finish at 20:00 instead of 21:00.

We talked about two things:
1) The time complexity of merge sort (n*log(n)).
2) The master theorem.

The master theorem basically gives the time complexity for divide-and-conquer algorithms. If you can write the time complexity of an algorithm in a specific recursive way then you can use the master theorem to get a bound on the time complexity of the algorithm.

We also got Test 1 back and handed in Problem Set 3. Problem Set 3 was not hard, you just needed to follow an example we saw in class and then you could get the closed form that was needed. I learned that a finite sum is not considered closed form if it grows in n. I was wrong to think that infinite sums are not considered closed-form but finite are.

Test 1 went OK. I made a stupid mistake that I now realize I was doing often when I was using the principle of complete induction. Need to be more careful from now on. Other than that, I was happy with my test.

I think I am writing just to avoid studying for CSC260 so I better stop here.

Week 5 - Thursday Oct 09, 2008

Attempt #2

Firefox crashed on me and took my post with it to the realms of the unknown. This re-post is going to be significantly shorter than the previous one because I am still mad at Firefox...

Week 5 ended and Test 1 is a thing of the past. This week we looked at structural induction, a flavor of induction that I found both more challenging and more interesting. We also looked at more recursive formulas and their closed forms. Specifically we saw how the Fibonacci sequence is related to the golden ratio. Interesting stuff I tell you! It makes me want to see Pi again...

As for test 1, I found it fair. I finished just on time but it was mainly because of the way I function which is not the optimal way a human being should function.

I solved one of the questions using combinatorics and I am sure it was because of the ternary trees problem on the Assignment. For a couple of weeks now all I do is count stuff and make sure I subtract the duplicates! I think I did well, I will see if the TAs agree with me sometime soon.

Have a great weekend and happy thanksgiving to all!

Week 4 - Thursday Oct 02, 2008

This week was all about recursion and how it's related to induction. We looked at the Fibonacci sequence, a very interesting sequence that appears pretty much everywhere: in nature, in the golden ration etc.

We looked at the sum of n Fibonacci numbers and found that it's given by F(n+2) - 1. The interesting thing is that when defining the Fibonacci numbers, you need two base cases, but when we proved the formula above we only used one.

Test 1 is coming next Thursday so it's time for a quick review of everything we covered so far in the course. I should have done that over the weekend but I decided to just rest and spend some time with my family.