Weirdest Analyses Ever

This semester I had the fortune of taking Dr. Greg Frederickson’s CS 381 (Algorithms) class. And boy did I see weird stuff in there. Below, I have a list of analyses I say are downright the most non-obvious (and in a way beautiful to look at).

• Edmonds-Karp Algorithm (Max Flow in a network): This algorithm is the Ford Fulkerson’s algorithm that uses a BFS to compute the next augmenting path as opposed to a DFS and subsequently achieves a running time of O(|V||E|^2). The idea here is that an edge (u, v) can appear in an augmenting path as a critical edge when the distance of u from the source ‘s’ (I will use dist(u) to denote distance from the source henceforth)is less than dist(v). Now, once augmented, this path can appear in another augmenting path only when this condition is met. This only happens when we retract flow off this edge. That is, edge (v, u) appears in an augmenting path on our residual network. The result is,

  dist(v) = dist(u) + 1

  So, let us say, (u,v) gets another shot at making it in an augmenting path, the distances are:

  new_dist(u) = new_dist(v) + 1;

  But from the conclusion obtained from a previous step,

  new_dist(u) = dist(u) + 2;

  So, for (u,v) to show up as a critical edge, in an augmenting path time and again, the distance of u from the source needs   to be incremented by 2. We can only go as far a |V| – 2 from the source. Simple arithmetic shows us that an edge can show up as a critical edge at most (|V|  / 2 ) times in its lifetime. There are 2*|E| edges in the residual network. So we have |V||E| iterations overall. We do at most |E| work with each augmenting path. So, the overall complexity is O(|V||E|^2). Beautiful stuff indeed.

• Any problem reduction which is used to prove lower bounds. EMST has a lower bound of Omega(nlog(n)) because we can reduce sorting to EMST. Brilliant!

Overall, I have to say, CS 381 under GNF or Atallah at Purdue is a must. Our department is responding too aggressively to individuals with a very poor work ethic by allowing CS majors to graduate without a solid, super-hard algorithms course. Please make the most of the solid Theory group we have in our department. This is wrong, simply wrong and it is an insult to the field and to society when you let someone call themselves a “Computer Scientist” and they need to look up wikipedia to analyze the performance of a breadth first tree traversal. Overall, I am not sure I am happy with the way the new curriculum is shaping up.