This is the first in a series of two posts about a study group I organised for learning Algorithms & Data Structures. This post focuses on the content of the course, which is Princeton’s Algorithms I on Coursera.
The course covers a variety of data structures and searching and sorting algorithms from a programmatic implementation angle (as opposed to mathematic proofs; more on that in my second post). Specifically, this one covered union-find, binary search, stacks, queues, insertion sort, mergesort, quicksort, binary heaps, binary search trees and red-black trees, and a lot more.
The course has multiple types of content to help you learn:
- The major component is the video lectures, which form about 2.5 hours of content each week and present some algorithm theory
- Detailed lecture slides
- Exercise questions, which test you understand that theory
- Assignments, which make you put an implementation of an algorithm in practice
- Final exam (I haven’t done this yet, but I still have a few weeks.)
Officially, the course is 6 weeks long, and requires 6-12 hours a week of effort. I think most people in our group underestimated how much time this really takes from your life.
Good things about this course
The combination of lectures, exercises and assignments was a really good way to cover the material from different angles. If you appreciate structured approaches to learning, this will tick all the boxes.
Videos: All of the material is professionally shot and edited. The entire series is presented by Robert Sedgwick, who is a very good lecturer. There is a good level of detail and explanation for each algorithm, especially the animated walk-throughs of each sorting algorithm. You have the option of watching the videos at a faster speed on the Coursera website, and I chose to watch it at 1.25x most of the time, as Sedgwick speaks quite methodically but slower than I am used to. (If you download the videos, you can’t take advantage of this feature, and you also miss the interim quizzes in the videos). It’s very helpful watching videos instead of listening to a live person, as you can pause them and rewind whenever you need to.
Slides: The slides are great. Very detailed, well-laid out and with diagrams to illustrate various concepts. The only thing missing from the slides were the animated walk-throughs of how each algorithm works, but you can always re-watch the videos.
Interim quiz: at the end of each video, and sometimes in the middle, you have to answer a question about the content you just watched.
Discussion boards: The Coursera site includes discussion boards where you can post questions. They’re monitored by people at Princeton who are helping to run the course. It’s a great resource when you get stuck.
Auto-marking for assignments: Assignments are all auto-marked for each submission, and the results from marking are really detailed. Each submission is run though lots of tests, and it also analyses your usage of memory & time relative to input (i.e. are you using constant, logarithmic, linear, quadratic time, etc). I found this quite valuable.
Real-world examples: Discussions of practical implementations of algorithms, such as a physics engine for particles, or easily finding whether lines/objects intersect, were really interesting.
Credibility: Sedgwick is a professor at Princeton’s school of Computing Science. You’re hearing from one of the people who has spent a lot of their life studying and working with algorithms – he’s written several books on algorithms, one of which is used as a reference for the Coursera course (the content is available for free on a corresponding book site). He also found a more efficient variant of Red-Black Trees in 2007, which he discusses in the lectures.
Choose your level of participation: You can cut out various parts of the course if you prefer – for example, if you were to only watch the lectures and make your own notes, you could spend 3 hours a week doing this course and still get something out of it. The minimum I’d recommend is watching the lectures and doing the exercises, as the exercises force you to step through the algorithms and work out what they’re doing.
Language-independent: It’s possible to complete these assignments in different langauges, as our study group proved. We had people write solutions in Rust, Python, Golang, C# and Scala. However, the majority of them completed in Java to take advantage of the auto-marker for the assignments.
Things I’d change about this course
Assignments not geared for unit testing: The APIs for the assignments were quite strict – it was almost impossible to test using dependency injection, or trying to refactor one giant (public) method into smaller public methods so you could test them independently. I did write some tests, but I also ended up submitting assignments to the auto-marker to get feedback for some aspects. I’d prefer if the API was less strict so that you can package your own classes, and break things into smaller chunks.
The assignments vary in complexity. Some require only 2 or 3 hours; others could take another 10 hours just by themselves.
Course schedule: The start date and schedule of the course is advertised as fixed, and quite intense. When they say you need 6-12 hours, they do mean it (and more). In reality, all assignments and lectures have “hard” and “soft” deadlines, and can be submitted up to 6 weeks after the lecture is released. If we had known, we would have built some catch-up weeks into our study group dates to allow people to keep pace. This isn’t Cousera’s fault, but some knowledge that the content would be around for ~3 months would have helped plan a better schedule for our study group.
Some content not as relevant: This is a personal preference, but the course covers a lot of different searching and sorting algorithms in depth; in reality only a handful of them are in use by major languages. I’d prefer to concentrate on the ones in use, and not cover the ones that have been superseded.
The course was intense, but I learned a lot and it helped connect some dots on how to solve particular types of problems. For me, the best moment was an email from Aidan, one of our study group members, in the last week:
I actually used a weighted quick-union at work yesterday! I‘m as shocked as everyone else.
Proof that it is actually relevant 🙂
As for Algorithms Part II, I’m sadly stretched working on various things in life, including this blog, Women Who Code Sydney and organising a variety of things with my work at the ABC. However, Caspar Kreiger is continuing the second half starting this week, so get in touch if you’re interested! I plan to pick up Part II in October when it is run again.