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.
Saturday, October 27, 2012
Sunday, October 14, 2012
Time Complexity
I still do not quite understand time complexity stuff in Friday's lecture, especially the slides below. I will try to figure out as soon as possible on weekdays.
Now I understand all those stuffs after finishing Assignment 2. First, n stands for the input size, and we need to use divide-and-conquer method to find the time complexity of this algorithm. For simplicity, we assume n = 2^k,and we can easily get the time complexity for that certain input. The calculation for n != 2^k needs more work and we must use other tricks (like sandwich theorem) to figure it out.
Now I understand all those stuffs after finishing Assignment 2. First, n stands for the input size, and we need to use divide-and-conquer method to find the time complexity of this algorithm. For simplicity, we assume n = 2^k,and we can easily get the time complexity for that certain input. The calculation for n != 2^k needs more work and we must use other tricks (like sandwich theorem) to figure it out.
Monday, October 8, 2012
Start to think like a computer scientist
Now since I am in csc236 course for a month, it is time to summarize what I have learned there, especially some new recognition about computer science.
The story began from this summer. When I spent my summer vacation in my hometown, Beijing, I met a friend who studies computational algorithm. He is currently under the mentorship of the Turing award winner Andrew Yao, and has already learned about NP completeness and Cook-Sullivan theorem a bit. He started to show me everything about that theorem and knowledge that associated with NP completeness after knowing that Cook is teaching in my university. It was the first time that I began to recognize the magic of algorithm and I spent several weeks just trying to absorb some basic ideas of those algorithm like what is a Turing machine. Algorithm is really difficult and very abstract, for we can seldom find a real-life example to illustrate it. So at that time I regarded computer algorithm as a combination of tons of abstract concepts, mostly related to time complexity, and it could only be used to reduce the amount of time consumed by a few complex calculation. But meanwhile, some algorithms, especially those related to NP and even P-space questions are a kind of way to test which level our human intelligence could reach, and it is far interesting to know about things that the most intelligent people are studying on. Therefore, I felt a little bit disappointed when knowing that we had to spend several weeks on those simple(literally, not terminologically) inductions. But after a few weeks I found that inductions were not as simple as I thought because using induction smartly we could solve lots of complicated questions easily, and they were all evolved with a fundamental thinking pattern for computer science: recursive thinking.So I realized the reason why I found data structure stuff in csc148 was hard was just because I could not think recursively, in other words, I could not think like a computer scientist. Now I have already known that I have to get a good command of those induction patterns, and try to think about hard questions recursively using a proper induction method. Still a long way to go from induction to Cook theorem, but I will think like a computer scientist right from the starting point.
The story began from this summer. When I spent my summer vacation in my hometown, Beijing, I met a friend who studies computational algorithm. He is currently under the mentorship of the Turing award winner Andrew Yao, and has already learned about NP completeness and Cook-Sullivan theorem a bit. He started to show me everything about that theorem and knowledge that associated with NP completeness after knowing that Cook is teaching in my university. It was the first time that I began to recognize the magic of algorithm and I spent several weeks just trying to absorb some basic ideas of those algorithm like what is a Turing machine. Algorithm is really difficult and very abstract, for we can seldom find a real-life example to illustrate it. So at that time I regarded computer algorithm as a combination of tons of abstract concepts, mostly related to time complexity, and it could only be used to reduce the amount of time consumed by a few complex calculation. But meanwhile, some algorithms, especially those related to NP and even P-space questions are a kind of way to test which level our human intelligence could reach, and it is far interesting to know about things that the most intelligent people are studying on. Therefore, I felt a little bit disappointed when knowing that we had to spend several weeks on those simple(literally, not terminologically) inductions. But after a few weeks I found that inductions were not as simple as I thought because using induction smartly we could solve lots of complicated questions easily, and they were all evolved with a fundamental thinking pattern for computer science: recursive thinking.So I realized the reason why I found data structure stuff in csc148 was hard was just because I could not think recursively, in other words, I could not think like a computer scientist. Now I have already known that I have to get a good command of those induction patterns, and try to think about hard questions recursively using a proper induction method. Still a long way to go from induction to Cook theorem, but I will think like a computer scientist right from the starting point.
Subscribe to:
Posts (Atom)