A few weeks ago I mentioned completing Part 1 of the online Coursera/Stanford “Algorithms: Design and Analysis” course. Part 2 of Algorithms: Design and Analysis isn’t due to start again until next year, but I didn’t want to wait, so I enrolled in the archived version of the course to watch the videos and do the assignments. I should be ready to just reuse my work when Part 2 starts again for real.

Part 2 was where things got really interesting. The assignments required implementing these algorithms, though the course covered others too:

- A
**Greedy Algorithm**for job scheduling. **Prim’s**and**Kruskal’s**minimum spanning tree algorithms. (Both O(m log n) but Prims does better on dense graphs, with more edges.)- Modifying a minimum spanning tree to identify
**clusters**. - The
**Knapsack**problem (**Dynamic Programming**– both bottom-up and recursive). - Shortest Path with the
**Belmann-Ford**SSSP (**Single-Source Shortest Path**) algorithm (O(mn) and works with negative paths, but fails with negative cycles) as an alternative to Dijkstra’s Shortest Path algorithm (O(m log n) and works only with positive paths). **All Pairs Shortest Path**with the**Floyd Warshall**algorithm (dynamic programming) (O(n^{3}) and works with negative paths, though it fails when it detects negative cycles). Best for dense graphs.**All Pairs Shortest path**with**Johnson’s**algorithm, via one call to Belmann-Ford on a modified graph and repeated calls to Dijkstra on a reweighted graph. (O(mn log n) and works with negative paths, but fails with negative cycles.) Best for sparse graphs.- A dynamic programming algorithm for the
**Traveling Salesman Problem**. **Local search**with the**2Sat**problem, using**Papadimitriou’s Algorithm**.

I particularly enjoyed exploring “dynamic programming”, which is really just avoiding unnecessary repeated work after you’ve identified the appropriate sub-problems. It’s identifying the sub problems that is really hard. I enjoyed playing with bottom-up dynamic programming (filling in an array as you go, often discarding the n-2th set of results as you go), and top-down dynamic programming, also known as memoization (usually recursing into sub problems and ideally not doing as many sub problems as you’d do working bottom up).

While implementing a dynamic programming solution for the Traveling Salesman Problem, I learned about Gosper’s Hack for iterating over subsets. It’s now a personal favorite in my toolbox.

As with part 1 of the course, I am not allowed to publish the code of my homework solutions. But I did create a public version of the knapsack problem for solving the Make Change problem without a canonical currency (not a real world set of coins), using dynamic programming, though you shouldn’t use that as a first way to understand the classic knapsack problem. I also implemented a simple greedy algorithm for the Make Change problem with a canonical currency (real world set of coins).

The Make Change problem was interesting because I’ve read that people can and should learn to recognize NP-Complete problems, such as the traveling salesman problem. However, it is not obvious which sets of coins would cause the Make Change problem to be solvable with a greedy algorithm and which would need dynamic programming, though it might at first seem like a minor detail. (I haven’t actually read that paper yet.)

I’ve also been reading through Steven Skiena’s The Algorithm Design Manual book, which I can highly recommend. It’s more practical and enjoyable than the classic Introduction to Algorithms book by Cormen et al.

**Update:** I did part 2 for real when it started again. Here is my certificate:

Slight typo: Floyd-Warshall is O(n**3), not O(n**2).

Thanks. Yes, of course.