Algorithms Part I & II from Princeton | My Review

Last year completed the following Princeton courses on algorithms via the Coursera platform:

• Algorithms, Part I
• Algorithms, Part II

In its own words, Coursera offers the world’s best courses, online, for free.

I’ve completed several Coursera courses and these two, along with Programming Languages are the best courses I’ve completed.

The instructors are Kevin Wayne and Robert Sedgewick. The former being very active within the course discussion forums and the latter presenting all of the video lectures. Part I & II are separate courses that make up the overall module, with each part spread over ~6 weeks. It’s said that this course is closely related to the mandatory algorithms module for Computer Science undergraduates at Princeton.

The standard of teaching material from the video lectures, slides and accompanying website was excellent. The way in which each week’s new concept built upon the previous week’s was so well structured it was like a well played game of chess.

Each week consisted of ~2 hours of lectures and was accompanied by exercise questions and the main event; a programming assignment to be written in Java. The assignments focused on choosing an appropriate algorithm to solve a large problem based on its characteristics as opposed to just coding a generic implementation of a linked list, binary tree etc. As well as correctly solving the problem presented there were also timing and memory constraints that had to be met in order to achieve 100%. Some took me around ~4 hours to complete and others I lost track of how much time I spent tweaking my solution to meet the benchmarks for 100%.

What did I get out of this Course?

Aside from the sense of achievement in completing all the assignments, I learned a lot. Some of the assignments required coding string compression techniques, Seam carving for images, graph processing, solving games like Boggle and 8 puzzle for large problem sets, geometric problems and more.

The only downside to this course is that Princeton offer no record of achievement. Although, in my opinion having the knowledge is more important.

Completing this course has made me a better developer.

Advice for taking this Course

By the end of the course I had adopted the following strategy for each week:

• The course introduction states that this course takes “6-12 hours of work per week”. From my own experience (and reading the course forum) some weeks you may spend more time than this. For me this extra time was spent chasing 100% for a programming assignment.

• View the lectures, read the programming assignment instructions but don’t start it. Answer the exercise questions relating to algorithm sequences on pen and paper first e.g. map each steps of a sorting algorithm. To pass the speed & memory benchmarks you need to be able to fully grasp the characteristics of the algorithm being used and this initial pen and paper work is perfect for this. I spent the most time on assignments where I lost discipline and jumped straight into coding.

• All the assignments require code written in Java. If you’ve done any type of statically typed programming before i.e. C# then the transition will be seamless.

• Don’t get too tangled up with the performance aspects on the first iteration. Go for correctness first, since getting a working solution will earn you around ~70%.

• Write unit tests as you go to verify that you have a working solution and catch regressions.

• Once correctness is achieved start to iterate your solution to meet the performance requirements. The tests you have will speed up this process tremendously.

• If you haven’t quite made it to 100%, move onto the next week and revisit later or you run the risk falling behind.

• I had to remind myself this important rule on a few occasions when I was stuck: formulating the question is 80% of the battle.

My Programming Setup

I used Sublime Text 2 for coding rather than the Dr. Java application provided for the course. I would have a small bash script for compiling and running tests.

NB I wouldn’t do this for a large real-world app however this light-weight approach was perfect to create a quick feedback loop for small classes.

Using the following class as an example:

public class HelloWorld {

	public boolean sayHello() {
		return true;
	}

}

I would work by running the following script from the terminal:

#!/bin/bash

checkstyle-algs4 HelloWorld.java

javac *.java

# JUnit Tests
javac -cp .:/usr/share/java/hamcrest-core-1.3.jar:/usr/share/java/junit.jar tests/*.java
java -cp .:./tests:/usr/share/java/junit.jar:/usr/share/java/hamcrest-core-1.3.jar org.junit.runner.JUnitCore HelloWorld

# this can be slow, so comment out until submission
findbugs-algs4 HelloWorld.class

There are no requirements to create tests in order to pass an assignment, it’s just a best practice. The use of JUnit is a personal preference.

Here is an example test using this approach:

import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;

import org.junit.Test;

public class HelloWorldTests {

   @Test
   public void saysHello() {
      HelloWorld hw = new HelloWorld();
      assertEquals(hw.saysHello(), true);
   }

}

Summary

I highly recommend this course to sharpen the saw for those core Computer Science concepts. It was challenging but very rewarding, especially when you get to see the following via the auto-grader: