## Final Review: Chapters 1 to 4

**Stable Matching, Marriage:**

Given some sets M = {m_{1}, … , m_{n}} and W = {w_{1}, … , 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.

## Tired? Sleep instead!

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

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

## Lecture 34: Knapsack Approximations

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 w_{i} and a value v_{i}. 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(v

_{i}in S) <= sum(v_{i}for all i) <= nv^{*}, where v^{*}= max v_{i}

Therefore, the algorithm runs in time O(n^{2}v^{*}).

**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) = w_{n} + Opt(n-1, V-V_{n})–so, just take the minimum:

Opt(n, V) = min({Opt(n-1, V), w

_{n}+ Opt(n-1, V-V_{n}})

There are some table bounds to consider:

Opt(1, V) = w

_{1}if v_{1}>= V, else infinity

Opt(k, 0) = 0

Opt(k, < 0) = 0

Finally, we can write the algorithm outline:

Knapsack0Approx(e):

b = (e/n) * max(v_{i})

for all i v_{i}^{^}= ceil(v_{i}/b)

solve problem with v_{i}^{^}via DP outline above

return result set S

## Lecture 33: Approximation of Vertex Cover

Let x_{i} be 0 if v_{i} is not in the Vertex Cover, and 1 if v_{i} is in the Vertex Cover. (v_{i}, v_{j}) is an edge such that x_{i} + x_{j} >= 1. We want to make the sum of all x_{i} 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:**

x_{i} >= 0

-x_{i} >= -1

x_{i} + x_{j} 7gt;= 1 for all (v_{i}, v_{j})

minimize sum(x_{i})

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.

**Approximation:**

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*x_{i} in S) = s * sum(x_{i} in S) <= 2 * sum(x_{i} from i = 0 to n) <= 2 * |S*|. So, we are within a factor of two of the optimal solution.

00Comments