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.