Coursera - Algorithms, Part 1 by Sedgewick and Wayne

Wan Kong Yew

Wan Kong Yew is a Malaysian national living in Kota Kinabalu. His concept of consciousness, in the vein of Denett, Egan and Marvin Minsky leads him to be interested in Computer Science and Information Theory. He maintains 2 blogs, his personal one  - Call To Reason and the other being a gaming one  - Knights of the Cardboard Castle.

As someone with no formal education in programming and treats the subject only as a hobby, I approached the Algorithms, Part 1 by Robert Sedgewick and Kevin Wayne of Princeton University with apprehension. As it turned out, I was right to be afraid but it also ended up being one of best learning experiences I have ever had.

This was Part 1 of a two-Part course covering material laid out in the 4^th edition of the textbook written by the two professors, also simply called Algorithms. The stated objective is to teach the 50 algorithms that all programmers should know, complete with analysis of each of their performance profiles.

The 6-week course discussed two topics every week, with a quiz for each topic. There was also a programming assignment for each week except for the last one, which instead had a final examination. For students wishing to explore even more deeply into the subject, the course also offered a set of the questions that one might expect to encounter in a typical job interview. These questions were ungraded and no answers were provided for them.

Professor Robert-Sedgewick

The full list of subjects covered in the six weeks is as follows:

• Union-Find
• Analysis of Algorithms
• Stacks and Queues
• Elementary Sorts
• Mergesort
• Quicksort
• Priority Queues
• Elementary Symbol Tables
• Balanced Search Trees
• Geometric Applications of BSTs
• Hash Tables

All five of the programming assignments were non-trivial though I am quite proud to state that I completed each of them with full marks. The one I had the most trouble with was finding collinear points, due to the difficulty of thinking about the problem in geometrical terms. Arguably the one that I had the most fun with was using the A* search algorithm to solve the 8 puzzle.

Generally speaking, the assignments asked you to write two solutions for the problem at hand, first a simple brute-force solution and then an efficient solution using the correct algorithm. This has the useful effect that you can always double-check the results of your efficient solution against the results of the brute-force solution as the latter will always be correct, albeit being terribly slow.

Grading of the students’ programs was done using an automated grader which checked to see that the API specifications were complied with, that the program worked correctly and that it did everything within the stipulated time and memory limits. Although the professors stated that their intent was to limit each student to ten attempts per assignment, the Coursera platform never enforced this restriction and many students ended up submitting many, many times.

The lecture videos are uniformly excellent. Only Professor Sedgewick appeared in the videos and he always explains everything clearly and succinctly. The videos are accompanied by animations of the algorithms in operation which must have taken a great deal of work to make but help student comprehension immensely. Furthermore all slides used in the lectures were provided in PDF format each week.

At the same time, Professor Wayne was active on the official forums and was always on hand to answer questions and resolve bugs in quiz questions and autograder errors. The atmosphere on the forums was great and everything was very well organized with each assignment of each week having its own sub-forum.

I greatly enjoyed the competitive spirit in the forums and joined others in improving our submitted programs above and beyond the assignments’ specifications. For example, the final stress test of the collinear points assignment required your program to run it in less than 10 seconds. My first submission clocked in at just under 7 seconds but my final submission came in at just under 3 seconds. The very best students were able to post times of less than 2 seconds.

The final exam involved a great deal more work than I expected and was suitably challenging. I believe it generally takes between 3 and 5 hours to complete all questions. Thankfully the final examination was untimed though we were limited to three attempts. One great thing about this exam as well as the weekly quizzes is that the questions were generated randomly. Apparently there were so many possible permutations of questions that the professors had no problems with students posting the questions and discussing answers on the forums. The only thing forbidden was posting source code for the assignments.

Finally, in case any people are wondering this course ran almost concurrently with the very similar Design and Analysis of Algorithms class by Tim Roughgarden of Stanford. Many students wondered about the difference between the two courses and Professor Wayne was kind enough to answer that the two courses are complementary as the Princeton course is more focused on practical applications while the Stanford course is more focused on theory.

As previously stated, this was a fantastic learning experience and I am immensely grateful for the opportunity to take this class. Professor Sedgewick is after one of the leading academics in the field and there is something so humbling about learning a subject while knowing that this professor is the very same person who wrote some of the research papers referenced in the course. His doctoral thesis advisor was after all none other than the legendary Donald Knuth. It just can’t get any more awesome than this.