Week 2 of Algorithms Part II. MST and Shortest Path

I finished the second week's work for Algorithms II from Coursera.

I had a three day weekend, so I was able to finish the lectures/exercises/programming assignment before the week even started.

We covered Minimum Spanning Trees and Shortest Path algorithms.

For Minimum Spanning Trees, we used Kruskal's algorithm and Prim's Algorithm. I have a hard time remembering what these algorithms refer to. Naming algorithms after a person is nice for that person, but it's a bit pointless. It's like naming a variable in a program after the original coder. It definitely wouldn't pass a code review.

In any case, Prim's algorithm works by doing the following:

Choose a node to start from.
Find the shortest edge that connects it to some other node.
Now, we have a two node component.

Then, repeat the following two steps.
1. From the component, find the shortest edge that connects it to an
   unconnected node.
2. Add that edge and component.

Kruskal's algorithm is a little bit different.

1. Sort the edges from shortest to longest.
2. Choose the shortest edge.
3. Use it if it is making a new connection.
4. Choose the next shortest edge and repeat from step 2.

I think better names for these might be, "NextBestNode" and "NextBestEdge".

Dijkstra's algorithm is an extension of Prim's algorithm where you consider the directions and weights to get the shortest paths.

A key idea in all of these algorithms is to keep building from basic tools. Use things like sorting, priority queues and depth-first or breadth-first iterations, along with some simple arrays for flagging changes and you can come up with some powerful algorithms.

This is demonstrated in the programming assignment. Using a shortest path algorithm with breadth-first searching we're able to do some rather cool image manipulation called seam carving.

This week was fun and cool, but I'll have to go back and review it all so that it really sticks with me moving forward.