COMS 482: unofficial class blog

Final Review: Chapters 1 to 4

Posted in Exams by Elliott Back on May 14th, 2005.

Stable Matching, Marriage:

Given some sets M = {m1, … , mn} and W = {w1, … , wn} 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
(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 Ii. For every interval Ibad before Ii that overlaps it, remove Ibad’s label from consideration. Then, assign a non-excluded label to Ii, 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 di > dj 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

  • 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

  • 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}

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.

Tired? Sleep instead!

Posted in Announcements by Elliott Back on April 25th, 2005.

Can’t get up at 8:00 AM to get to class? Do you keep falling asleep to the lullaby of “NP….?” Do you look like:


If you answered yes to any of the above, then this blog is for YOU! Get all your CS 482: Algorithms notes here, free, always!

Lecture 35: Knapsack Approximation Proofs

Posted in Class Notes by Elliott Back on April 22nd, 2005.

In the previous lecture we showed an approximation to the Knapsack algorithm that is fast when v* = max vi is small. So, convert a knapsack problem into one where v* is small by choosing b and converting vi -> ceil(vi/b). We want an answer within (1 + e) of the true value, so b = (e/n) * v*.

Lecture 34: Knapsack Approximations

Posted in Class Notes by Elliott Back on April 20th, 2005.

Some approximation bounds so far:

  • Makespan: 3/2, 4/3
  • Center selection: 2
  • Vertex cover: 2

The goal is to achieve a (1 + e) approximation.

Knapsack Problem:

We can carry at most W weight. We have n items to choose from, each with weight wi and a value vi. Our goal is to maximize value without exceeding weight boundary W. Using Dynamic Programming, we can define:

Opt(i, V) = smallest weight possible using items {1, …, i} and choosing value >= V.

Given the Opt(*, *) function and W, we can search the opt-table to find the largest V for which opt(n, V) <= W:

V = sum(vi in S) <= sum(vi for all i) <= nv*, where v* = max vi

Therefore, the algorithm runs in time O(n2v*).

Algorithm notes:

If the nth item is not in opt solution, then Opt(n, V) = Opt(n-1, V). If the nth item is in the optimal solution, then Opt(n, V) = wn + Opt(n-1, V-Vn)–so, just take the minimum:

Opt(n, V) = min({Opt(n-1, V), wn + Opt(n-1, V-Vn})

There are some table bounds to consider:

Opt(1, V) = w1 if v1 >= V, else infinity
Opt(k, 0) = 0
Opt(k, < 0) = 0

Finally, we can write the algorithm outline:

    b = (e/n) * max(vi)
    for all i vi^ = ceil(vi/b)
    solve problem with vi^ via DP outline above
    return result set S

Lecture 33: Approximation of Vertex Cover

Posted in Class Notes by Elliott Back on April 18th, 2005.

Let xi be 0 if vi is not in the Vertex Cover, and 1 if vi is in the Vertex Cover. (vi, vj) is an edge such that xi + xj >= 1. We want to make the sum of all xi as small as possible, and still cover the edges.

Linear Programming:

A set of linear inequalities define a feasible region, for example:

x + y >=0
x – y >= 0
x <= 5
y <= 2

Or, in matrix form:

[[1,1][1,-1][1,0][0,1]] * [[x][y]] >= [[0][0][-5][-2]]

The goal is to remain the feasible region while optimizing something. In general, given {Ax = b}, a set of linear inequalities, we want to minimize c*x, i.e. find the minimum {c*x | Ax >= b}. Geometrically, this is finding the extreme point of a polytope. We can write this as a decision problem, too. Given A, b, c, and a bound B, is there a solution x such that Ax >= b and c’*x <= B?

Claim: “LP is in NP”

Given a set of values, we can check the solution in polynomial time. Rational numbers, however, require additional book keeping. Beware! Also, LP is in Co-NP and in P, using an interior point method.

VC as a LP problem:

xi >= 0
-xi >= -1
xi + xj 7gt;= 1 for all (vi, vj)
minimize sum(xi)

Then, run LP but only allow integer solutions. This is called “Integer Programming” (IP). Claim: “VC <=p IP.” Rewrite VC as an IP problem, then the solution to one implies the other. Claim: “IP is in NP.” Obvious. Therefore, IP is NP-Complete.


Simply round the LP solution to get integers. S = {i | i >= 1/2}, our approximate vertex cover. Then, |S| = sum(i in S) <= sum(2*xi in S) = s * sum(xi in S) <= 2 * sum(xi from i = 0 to n) <= 2 * |S*|. So, we are within a factor of two of the optimal solution.

Next Page »