Week 6 - Complexity of Merge Sort Master Theorem

I was never good with sorting in first year, especially merge sort. Now that it's being touched on again, I think I should spend more time on it this time. Merge sort is an instance of a general strategy: divide up a problem into subproblems of the same type, and then combine the solutions to the subproblems. The "smallest" instances of the problem can be solved directly. This is a useful strategy, and it sounds similiar to the principle of induction. But overall, I was quite lost during this lecture, it's time again to do some studies at home.

I also received my test back this week... very shocked by the speed of marking. I was VERY disappointed with my test result however, I thought I did pretty well. But it turns out that my careless mistakes killed me hard. I lost tons of marks on what I thought was the easiest question... This test has definitely rang a bell: be more conscientious next time! Though I think I will be asking for a remark, the almost 30% deduction was too harsh for a careless mistake.


PROBLEM SET #3

After unwinding the function, I couldn't find a pattern to make a conjecture about a closed-form for it. This question seemed very hard until my friend gave me a hint as to what the pattern is. It wasn't obvious to me at all. What if the same question comes up on the test and I don't have all that time to look for a pattern? Or what if I get totally stuck like this time? Maybe doing more practice problems will help.

Week 5 - Closed Form of Recurrence, Structural Induction, Gcd

The closed form of recurrence seems really confusing at the beginning due to all the complicated symbols, it took me quiet a while to figure out. But once I got the hang of it, the technique was not too hard to apply at all. The next topic, defining sets with induction, is not that hard either. The definition itself gives a hint as to what base case to use and what assumptions to make when doing induction proves.


TERM TEST #1

Overall, I think this is a very reasonable test. It was similar to what I have expected based on the past midterm. All three questions were about induction, and I don't think they are too difficult to solve. After finding out about the base case, the prove seemed very straight forward to me. I think I can expect an A from this test.

Week 4 - Recursive Definitions

In short, recursion is just a special case of naming. When a definition includes the name we give to the entire definition itself, we have recursion. This topic is not a hard one, though sometimes it is not easy to find the pattern when unwinding. Other than that, I just have to be extra careful when defining a function, not to miss out on any cases and make sure it is a recursion based on previous elements. The topic on time complexity is the one that caused most trouble for me this week. After reading the slides over and over again, I still can't seem to understand how to calculate the time complexity of a function. For this, I am going to ask for help from some friends, and if that doesn't work, I will go talk to the TAs next week.


ASSIGNMENT #1

Also, this is the week that assignment 1 is due. I was expecting the assignment questions to be on the same level of difficulty as the problem sets, but I was wrong. The first question was ok, but the second and third question took me quiet a while to figure out. I was stuck on figuring out a general technique for making the lunch menus for a long time. The TAs at the Help Center were a great help. They made the question look so easy. I guess I was just thinking too much.... Oh, one other thing, I didn't start looking at the assignment sheet until the weekend, and I found it pretty rushed to get all of the questions done. I didn't hand in the assignment until the very last minute. For next time, I'll know to start working on assignments early, not going to leave it to the last minute again.