I recently attended Coursera course Algorithms: Design and Analysis, Part 1 by professor Tim Roughgarden from Stanford University. It was great. The course was well prepared and I have only the best things to say about it. This review is a mix of feelings about this concrete course and the Coursera itself, since this course was my first introduction to Coursera.
I had chosen this course because I studied electrical engineering and basically all I know about programming and computer science I have taught myself in my own time. I thought it would be a great idea to expose myself to what my colleagues had been exposed to while studying computer science, that is to an organized curriculum and a series of lectures with tests and all. And what a great decision that was! I was familiar with most of the subject covered, but this course gave me some mathematical aspect of the field that I didn't notice before, because I was always eagerly skipping non utilitarian points of view in undergrad computer science literature, that I was reading. And most of all, it was surprisingly fun, challenging and rewarding!
The subject was presented in a kind of easygoing, narrative way. It started with introduction to asymptotic analysis and then continued on to present divide and conquer paradigm and using just learnt asymptotic analysis to show why it is effective. After introducing us to some of the most used linearithmic sorting algorithms, the course continued on to graphs, connectivity, minimum cuts and shortest path problems. Everything was well explained, with examples of utilization of the algorithms in real-life problems alongside with understandable mathematical proofs. Professor Roughgarden makes the subject interesting and compelling. At shortest path it was shown, how the correct data structure can influence the complexity of the algorithms, and that was our introduction to heaps. From heaps, the subject went on to other data structures, namely hashing, bloom filters and binary search trees. This concluded the first part of this course.
I have always skipped mathematical proofs in my life, whenever I was able to, but here I really started to appreciate them. I remember the goosebumps I got when I got a grasp on the decomposition principle! This was to prove the average case complexity of quicksort. I have never looked at quicksort that way. It is amazing how completely random events can be proved to have a totally non random average performance just by employing some mathematical trick, namely indicator random variable . Wonderful, just wonderful!
I have probably been so inspired by these things because it is much easier to go through these proofs in a comfortable couch at home, whenever I felt like it, then it was, for instance, at 7AM at the university. Besides, I also watched some videos couple of times. I would never in real life have asked professor to repeat explanation, not even once, let alone three or four times! This is also the side benefit of online courses: no feelings of inadequacy when something is not understood at first attempt.
Lectures divided into small, short topics, probably about 10 minutes in average, are great idea. If I needed two hours of uninterrupted time for lectures I would have to plan the days accordingly, but 10 minut chunks are easy: two lectures with my morning coffee, one lecture at work during lunch time, 2 after dinner at home... one can easily watch all the required material in a week without even noticing how much time it really consumes. I was stunned at the end of the lecture, when I summed it all up and figured out that I just saw almost 20h of lectures during that time!
There is, I believe, one more advantage to short lectures. When you see one in the morning and then commute to work, then eat your lunch, go to coffee with coworkers, the idea you saw in the morning is slowly brewing in the head and it contributes to understanding. 10 minutes is enough to give some information and to spark interest, but not enough to make you tired, so it is easier to think about it and to try to internalize the subject. It is also so much more compelling to return to see other lectures.
One programming assignment each week was a great refresh after the theoretical work. I remember that at the university I was distracted many times by some practical idea that popped to my mind, because I was inspired by something I've just heard at the lectures. But that was really a bad thing in that environment, because while concentrating on practice, many times I lost the pace with the rest of the class. It was different here. Few lectures to cover theory, then immediately to putting the learned material to practical use. Here, this was not a distraction, but rather a desired behavior; my weakness was is a strength!
I was hooked on all those small rewards the Coursera system gives you all the time. In lecture quizzes, for instance. You answer one correctly and it immediately makes you feel a bit better about yourself. Then the feeling of understanding something new after you watched the video. Then the successfully completed quiz with desired amount of points each week. And the programming assignment, whose result gets accepted by the grading system, there's that feeling again. Each small lecture, each assignment, each week. They get you hooked on this small doses of dopamine on each small incremental step in learning, that in the process you forget how much effort it really takes. This is very unlike the official educational system, where you have to put in a lot of work, usually few months, before you get your first reward back. If. If not, there is few more months of work until the next quiz, that you need to persevere. It's different here. Instant gratification just pulls you in and failing on first attempt does not defeat you so easily, because it becomes a game.
It is amazing how great the quizzes were in this course. Each question approached the subject from lecture from a different perspective. I felt more intrigued, then tested for knowledge, and it was great fun. Each quiz felt like I was solving some sort of puzzle. At times I really had to think hard about the problem. It was not because I didn't remember the lecture. Remembering what professor said at the lecture, just so that I could feed that same information back to the quiz was not the point at all. For example, Dijktra's shortest path algorithm can't find shortest path's in a graph with negative edge lengths. First thought around this could be to add some value to each edge, just so that you remove negative values, then calculate shortest path, then subtract that value. That approach was shown not to work in the lecture and I understood well why. Now for the question from quiz: could Dijkstra return the right result if only the first outgoing edge from the start vertex would have a negative edge length? Yeah, that sort of puzzles. The sort that makes you feel smarter after completing it. I remember thinking whether it was lectures or the quizzes that brought more value to this course.
The programming assignments were not too hard, but were not completely trivial neither. They were nice demonstration of how smart use of algorithms can make a difference between approaches. I had been given a problem and the data set for it and I had to compute the result, which was at the end some number. It was this number that I had to submit, not the code itself. This approach made it possible for them to allow us to use any programming language, which is great. Students could focus solely on the algorithm and not on some specific prescribed programming language, that they might feel unfamiliar with. The problem sizes were big enough, so that naive implementations or any use of Excel and similar software was out of the question. I used C++ at first, but had to complete the course in C#, because I destroyed my C++ environment in the meanwhile (long story). It was interesting to see how other people approached this. I saw in forum that someone was programming assignments in PL/SQL! :) I mean, whatever works for someone, right?
Few days ago I finally received my signed Statement of Accomplishment for successfully completing this Coursera class, with 90% score. They got me hooked on learning. I'm already signed up for the second part of this course, I want more of this drug!
Previous:
Reversing graphs in Kosaraju's algorithm is in fact necessary
Next:
Why the name red-black tree?