Week 3 of Algorithms Part III. Mincut/Maxflow

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

I flew through the lectures and exercises over the weekend. The first set of lectures was on Mincut/Maxflow, and the second set was on Radix sort of strings. It looks like we are wrapping up our work with graphs and restarting work on strings.

I think the mincut/maxcut graph search algorithm is tricky. One example of applying this algorithm is calculating when a baseball team is mathematically eliminated from the playoffs. The programming assignment was based on this baseball problem. It was trivial to complete (we just used an existing API that calculated the maxflow), but it was still hard for me to wrap my head around.

I'll have to review the graph data structure and algorithms more, but it's cool to think that I've learned all the basics. I've always found graph structures to be intimidating. It may be an oversimplification, but here's what I'd say about most graph problems:

- maintain a list of neighbors. 
- do depth first or breadth first search.
- for a given problem, maintain some auxillary data, 
  like previous node or current weight

and that's about it. I should review the material to judge whether that's really an oversimplification or not, but that's what I'm feeling now.

After the mincut/maxflow stuff, the lectures moved to sorting again. Oddly, we studied radix sort, which is rather trivial compared to the more complicated merge/quick/heap sorts. I guess we are transitioning to other string algorithms, so this just a step in that direction.

And now, the course has a break for one week. I will take the week to go over material and the given job interview questions. And, rest.