I was just watching House of Cards, and I am at the episode that Peter Rosso was killed. I am so sad, I like that guy. I was hoping he would turn down that girl, I was hoping he never touches that whiskey, and I was hoping he never raises another bottle again. I was just thinking that how stupid he is to give up that easily, and trust somebody he shouldn't. Then I thought about myself, having my days filled with small stuffs, abusing my time on social network and TV. I might as well stop taking the "drink" myself.
Back to the algorithm course I want to talk about. The course ended last week, I cannot say I am doing great at this course, but I am happy with a grade that allows me to pass. This made it the first course that I passed from Coursera. It is not easy for me at all. I had only vague memory about my data structure and graph theory course, and this lecture forced me to review most of them. I choose C++ to be the programming language for the exercise, and this is particularly painful since my last time dealing with pointers is 6 years ago. And I started it when I was writing my master thesis (I finished the whole thesis thing 3 weeks before this course ended, otherwise I don't know if I can pass). So I think I am allowed to be proud that I passed.
There is a lot of compliment for this course online and they are speaking of my opinion. Hard content, nice structure, great lectures, and tough exercises. What I also see is that there is a lot effort in this course, I don't know exactly how much, but I know there is a lot. I occasionally view the Algorithm I archive because I haven't taken it. I can tell that there is a lot of progresses in Part II from Part I, although they come from the same professor, and really are close in time. This is a team that really works to make the course better and better. The TAs in the forum are awesome, I am very surprised at how well they know about algorithms and how devoted they are to answering questions from the students.
So what do I learn from the course. First, I got adapted to C++ though the exercises. I am far from an expert, but I am comfortable using C++. I also got a better sense on the memory that a program might use, partly thanks to my 2GB RAM. On the contrary, I care less about time. It is not to say that time is not important, but a large part of it has been taken care of by those "blazingly fast" algorithms we learned. For me, the bottleneck is always the memory.
Second, and I think more importantly, I have a better sense about algorithm. I used to view algorithms, or at least the algorithms course as just one part of computer science. You have to take it so you know how to program. But what I learned from the course is that single algorithm does not matter (of course, it would matter for a specific problem, but I mean to the knowledge of a person). I watched the course, I did the exam, I implemented the algorithms, but I am sure that I will forget most of the details right away if I don't use them. But that's not a problem. We will only use a few of the algorithms if ever, and we can always look them up when we need. The real issue is, through these examples, we know how to properly design an algorithm for a new problem, where should we start, what's the possible hint.
Third, about the designing paradigms, greedy algorithm, divide and conquer, dynamic programming. Greedy algorithm is, well, greedy. I think it would be the least useful in the real world since you have the make the right call every turn, there is no turning back and correct. Divide and conquer and dynamic programming are in themselves the same. The key issue is to break a problem down into smaller problems. The difference is that divide and conquer has much smaller subproblems, usually half the size of the original one, that's why in the running time there is always a log(n). I think it is always a nice way to think when we encounter a problem, can we break it down to smaller easier problems.
Fourth, the NP-complete. One third of this course is devoted to NP-complete. And this is the part that I least understand. I like the philosophical explanation for the P != NP, which is that checking if the answer is correct should be strictly much easier than finding the answer. I am also glad that this is still an open question. I always thought NP stands for N particles, which is also an unsolvable (or unsolved) issue, I wonder how they would connect. Among the 3 ways to deal with the NP-complete problem that Professor Roughbgarden proposed, I like the second one best which is instead of an accurate answer, we look for a "nearly the best" or even "not so bad" one with reasonable amount of resources. It outlines how people usually work with their problems. For real problems, I mean real problems in the real world, no one is doing brute-force search to find the best choice, this is usually unacceptably expensive if it is ever possible. Instead, people relies a lot on experience, on intuition. Nobody can say that they make the best decision overall, but usually people are doing OK, right? We want computer to think like human, maybe we should start by making it less good at math.
I couldn't help but think about the link between physics and algorithms. Is physics itself an algorithm? Is Newton's laws just the best algorithm for predicting the trajectories of stars, how we could approach this task otherwise, is there other maybe less efficient algorithms? What about the time axis that a physics problem usually have, does it make any difference to the algorithms we are learning? If the world is deterministic (this is an abandoned idea because of the finding of quantum physics and chaos, but nobody can actually know this for sure), meaning we have full prediction of the future if we have enough information about the present, does this lead to an algorithm solving the "Halting" problem? Or, does the restriction on the algorithms reflect the unpredictability in the real world?
Finally, thanks to the team of this course, I benefit a lot from it.
Back to the algorithm course I want to talk about. The course ended last week, I cannot say I am doing great at this course, but I am happy with a grade that allows me to pass. This made it the first course that I passed from Coursera. It is not easy for me at all. I had only vague memory about my data structure and graph theory course, and this lecture forced me to review most of them. I choose C++ to be the programming language for the exercise, and this is particularly painful since my last time dealing with pointers is 6 years ago. And I started it when I was writing my master thesis (I finished the whole thesis thing 3 weeks before this course ended, otherwise I don't know if I can pass). So I think I am allowed to be proud that I passed.
There is a lot of compliment for this course online and they are speaking of my opinion. Hard content, nice structure, great lectures, and tough exercises. What I also see is that there is a lot effort in this course, I don't know exactly how much, but I know there is a lot. I occasionally view the Algorithm I archive because I haven't taken it. I can tell that there is a lot of progresses in Part II from Part I, although they come from the same professor, and really are close in time. This is a team that really works to make the course better and better. The TAs in the forum are awesome, I am very surprised at how well they know about algorithms and how devoted they are to answering questions from the students.
So what do I learn from the course. First, I got adapted to C++ though the exercises. I am far from an expert, but I am comfortable using C++. I also got a better sense on the memory that a program might use, partly thanks to my 2GB RAM. On the contrary, I care less about time. It is not to say that time is not important, but a large part of it has been taken care of by those "blazingly fast" algorithms we learned. For me, the bottleneck is always the memory.
Second, and I think more importantly, I have a better sense about algorithm. I used to view algorithms, or at least the algorithms course as just one part of computer science. You have to take it so you know how to program. But what I learned from the course is that single algorithm does not matter (of course, it would matter for a specific problem, but I mean to the knowledge of a person). I watched the course, I did the exam, I implemented the algorithms, but I am sure that I will forget most of the details right away if I don't use them. But that's not a problem. We will only use a few of the algorithms if ever, and we can always look them up when we need. The real issue is, through these examples, we know how to properly design an algorithm for a new problem, where should we start, what's the possible hint.
Third, about the designing paradigms, greedy algorithm, divide and conquer, dynamic programming. Greedy algorithm is, well, greedy. I think it would be the least useful in the real world since you have the make the right call every turn, there is no turning back and correct. Divide and conquer and dynamic programming are in themselves the same. The key issue is to break a problem down into smaller problems. The difference is that divide and conquer has much smaller subproblems, usually half the size of the original one, that's why in the running time there is always a log(n). I think it is always a nice way to think when we encounter a problem, can we break it down to smaller easier problems.
Fourth, the NP-complete. One third of this course is devoted to NP-complete. And this is the part that I least understand. I like the philosophical explanation for the P != NP, which is that checking if the answer is correct should be strictly much easier than finding the answer. I am also glad that this is still an open question. I always thought NP stands for N particles, which is also an unsolvable (or unsolved) issue, I wonder how they would connect. Among the 3 ways to deal with the NP-complete problem that Professor Roughbgarden proposed, I like the second one best which is instead of an accurate answer, we look for a "nearly the best" or even "not so bad" one with reasonable amount of resources. It outlines how people usually work with their problems. For real problems, I mean real problems in the real world, no one is doing brute-force search to find the best choice, this is usually unacceptably expensive if it is ever possible. Instead, people relies a lot on experience, on intuition. Nobody can say that they make the best decision overall, but usually people are doing OK, right? We want computer to think like human, maybe we should start by making it less good at math.
I couldn't help but think about the link between physics and algorithms. Is physics itself an algorithm? Is Newton's laws just the best algorithm for predicting the trajectories of stars, how we could approach this task otherwise, is there other maybe less efficient algorithms? What about the time axis that a physics problem usually have, does it make any difference to the algorithms we are learning? If the world is deterministic (this is an abandoned idea because of the finding of quantum physics and chaos, but nobody can actually know this for sure), meaning we have full prediction of the future if we have enough information about the present, does this lead to an algorithm solving the "Halting" problem? Or, does the restriction on the algorithms reflect the unpredictability in the real world?
Finally, thanks to the team of this course, I benefit a lot from it.
