I have to admit that I didn't learn well in csc165 course, so as the course going on, I found it necessary to do some reviews on the 165 stuff.
When the professor mentioned Master Theorem, I thought Big Theta was lower bound, so I was totally confused about the stuff derived from that Theorem. So after class I looked up that concept using Wiki and found that Big Theta is both the upper and lower bound, namely tight bound. Then I suddenly came to understand the idea of Master Theorem: using that theorem you can know exactly the time complexity of Merge sort or other divide-and-conquer problems. Also I reviewed other stuffs such as Big Omega so that I could understand the course material better.
Wikipedia is a good reference for students. Since I am interested in computing discipline and algorithm, I often browse on Wiki to get something useful. For instance, when I looked up Big O notation on Wiki, I noticed a sentence in the introduction: "In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size." Initially I thought why people need algorithm was because people need to handle very very large input n by using a very very advanced billion-calculation-per-millisecond computer, but now I realized that very basic thing about computing algorithm.
I have already done the review of 165 stuff, but I will definitely do some preview or optional reading using Wiki.
No comments:
Post a Comment