Cheat sheet for final

I might add a few more things if I think of them tomorrow, but this is basically the note sheet I'm bringing to the Algorithms final tomorrow. Some of it doesn't translate well to HTML, but that's not something I need to be fixing now:

Breadth-First-Search

Q.Add(s)                                //s=start node

while not Q.Empty

                u = Q.Dequeue

                foreach v in G.adj[u]

                if ( v.color == WHITE)

                                v.color = GRAY      //in progress

                                v.d = u.d + 1

                                v.pi = u

                                Q.Add(v)

                u.color = Black                                         //done

Depth-First-Search

time = 0

foreach u in G.V

                if (u.color == WHITE)

                                DfsVisit(G, u)

DfsVisit(G, v)

time = time + 1

u.d = time

u.color = GRAY                                                                     //in progress

foreach v in G.adj[u]

                if (v.color == WHITE)

                                v.pi = u

                                DfsVisit(G, v)

u.color = BLACK                                                                   //done

time = time + 1

u.f = time

Kruskal MST

A = null

foreach v in G.V

                MakeSet(v)

sort(G.E by weight)

foreach e in G.E                                    //e = (u,v)

                if FindSet(e.u) <> FindSet(e.v)

                                A.Add(e)

                                Union(e.u, e.v)      //merge trees

Prim MST

Q = G.V

while not Q.Empty

                u = Q.ExtractMin

                foreach v in G.Adj[u]

                if (v in Q) and w(u,v) < v.key

                //v hasn’t been pulled in yet and this edge is

                // a better bridge to v than any we’ve seen

                                v,pi = u

                                v.key = w(u,v)

// at end, Q is empty, so everybody is in

Bellman-Ford Single Source Shortest Path

for i = 1 to |G.V| - 1

                foreach e in G.E //check EVERY edge – no particular order

                                Relax(e.u, e.v, e.w)

foreach e in G.E                                    //check for negative cycles

                if (e.v.d > e.u.d + e.w)         //dist to u + (u,v)

                                return false

Relax(u, v, w)

if (v.d > u.d + w)

                // if it’s faster to go through u, do it

                v.d = u.d + w

                v.pi = u

Dijkstra Single Source Shortest Path

//Requires non-negative cycles

S = null

Q = G.V

while not Q.Empty

                u = Q.ExtractMin

                S.Add(u)

                foreach e in G.adj[u]           //check adjacent edges

                                Relax(u, e.v, e.w)

Standard LP Form – n variables, m constraints

maximize sum(c_jx_j)

subject to

sum(a_ijx_j) <= b_i              i = 1, …, m

x_j >= 0                                            j = 1, …, n

OR

maximize c^Tx

subject to Ax <= b, x >= 0

Conversion to standard form

min rather than max: negate objective function

greater than constraint: negate and flip inequality

equality constraint: replace with Ax <= b and –Ax <= -b

missing non-negative variable constraint

                replace x with (x’ – x’’) where x’, x’’ >=  0

Slack LP Form – n variables, m constraints

s = b – Ax, s >= 0, x>= 0

s is Basic var: indices in B; |B| = m

x is Non-Basic: indices in N; |N| = n

v is value of objective function

YEILDS (N, B, A, b, c, v)

z              = v           + sum_N(c_jx_j)

x_i             = b_i          - sum_N(a_ijx_j) i in B //NOTE SUBTRACTION

Standard NPC-Reduction

1)       Show problem A is NP.

2)       Show reduction from known NPC B in P

3)       Show A iff B

NPC Taxonomy

Constraints – CIRCUIT-SAT, SAT, 3-SAT

Sequencing – HAM-CYCLE, TSP

Numeric – SUBSET-SUM, KNAPSACK(0,1)

Covering – SET-COVER, VERTEX-COVER

Packing – SET-PACKING, IND-SET(aka VERTEX-PACKING)

Partitioning – PARTITION, 3D-MATCHING, 3-COLOR

Approximation Ratio

max(C/C*, C*/C) <= p(n):: p(n) approximation algorithm

                (may be expected or actual cost)

(1+e)-approximation scheme::

for any e>0 (1+e)-approx algorithm

polynomial-time approx schem::

                for any e>0, polynomial in size n

fully polynomial-time approx schem::

                polynomial in n AND 1/e

General Identities

n^b = o(aⁿ)                //exponential crushes polynomial

lg^b n = o(n^a)           //polynomial crushes polylogarithmic

log_b aⁿ = n log_b a

log_b a = (log_c a) / (log_c b)

log_b (1/a) = -log_b a

log_b a = 1/(log_a b)

a^log_b^c = c^log_b^a