COMS 482: unofficial class blog

Stable Matching, Marriage:

Given some sets M = {m₁, … , m_n} and W = {w₁, … , w_n} representing men and women, we want to find a perfect stable matching.

• A matching is a set of ordered pairs in MxW such that every m, w appear at most once.
• In a perfect matching, each m, w appear exactly once.
• An instability occurs when there are two pairs (m, w) and (m’, w’) such that m prefers w’ to w, and w’ prefers m to m’.

Gale-Shapely Algorithm:

Initialize all m in M and w in W to free
while there exists free man m who still has a woman w to propose to {
w = m’s highest ranked such woman
if w is free
engage (m, w)
else some pair (m’, w) already exists
if w prefers m to m’
(m, w) become married
m’ becomes free
else
(m’, w) remain married
}

Termination is obvious. Show there are no instabilities by simple contradition. See Lecture 1 for more on Stable Matching / Marriage.

Breadth First Search:

BFS can be used to identify connected components as well as for testing bipartiteness of graphs. If there are no edges joining nodes in the same BFS layer, then the graph must contain an odd length cycle and be non-bipartite. For more about BFS, see lecture 7 on Breadth-First Search.

Greedy Algorithms:

• Interval Scheduling: Schedule non-overlapping requests to a certain interval, maximizing the size of the compatible set.
  

  Simply choose requests with the smallest finishing time, and delete all overlapping requests until done. Proof proceeds by “stays ahead” argument.

  See lecture 3 for a proof of optimality.

• Interval Partitioning: Schedule all intervals across a minimal number of resources so that none of the intervals scheduled to a particular resource overlap. The number of resources needed is at least the maximum depth of the set of intervals.
  

  Sort the intervals by start times. Assign a label to the first interval. Then, choose the next interval I_i. For every interval I_bad before I_i that overlaps it, remove I_bad’s label from consideration. Then, assign a non-excluded label to I_i, if there is one.

• Scheduling to Minimize Lateness: Sort by the earliest deadlines and schedule in this order.
  

  There’s an optimal schedule with no idle time–our algorithm also has no idle time. If there is an inversion in the optimal solution, there d_i > d_j and j is scheduled after i. If we swap i and j, we keep the same lateness, so the greddy algorithm is optimal by an exchange argument.

• Dijkstra’s Algorithm: Find the shortest path from a given node to all other nodes (Single Source Shortest Path, SSSP):
  

  Choose a start node s in V
  PQ.put(s, 0)
  While PQ != {}
  (u, d) = PQ.getMin()
  if u is done then continue
  mark u as done (or report (u, d))
  for v adjacent to u do
  PQ.put(v, d + dist(u,v));
  end for
  end while

Greedy MST Problems:

• Kruskal’s Algorithm:
  

  Sort edges by cost
  T = {}
  for e in edges do
  if e does not create a cycle then
  add e to T
  endif
  endfor

• Prim’s Algorithm:
  

  Choose a start vertex s
  T = {s}
  While there is a vertex not in T do
  choose least cost edge from T to some vertex not in T
  add this edge to T
  endwhile

• Reverse Delete Algorithm:
  

  Sort edges by cost, decreasing
  T = E, the edge set
  for e in T do
  if removing e does not disconnect the graph then
  T = T - {e}
  endif
  endfor

All of these MST algorithms can be implemented in O(m log n) time. Lecture 4 contains a proof that Kruskal’s algorithm produces an MST, lecture 5 proves the same for Prim’s algorithm, and lecture 6 carefully proves the time complexity of Kruskal’s algorithm.

Two interesting MST facts:

• The most expensive edge of a cycle on G is not in any MST
• The min cost edge between V-S and S, where S is a strict subset of V, is in the MST

Also, make sure you know how union find operates, replacing parent pointers with a pointer to the root on find() operations, and joining trees smaller to larger on union() operations to keep the trees balanced.