UNC COMP550 Final Sun

Max in array

Basic, O(n), basic scan

Array sort

Basic, O(nlogn), QuickSort or MergeSort

Two sum array

Basic, O(n) if sorted, O(nlogn) otherwise. Two pointers, move toward center to achieve given sum, fail if pointers exceed each other.

BFS (Breadth first search)

Graph shortest paths, O(n+m), search one "layer" of vertices and then the next, keeping queue of next vertices to process.

DFS (depth first search)

Graph shortest paths, O(n+m), "rat maze," keep "time" values in pre[] and post[] arrays

Prim's

MST, O(n^2). Build cut directly; keep adding the lightest edge crossing the cut without causing cycles.

Kruskal's

MST, O(mlogm). Build MST from graph directly, sort edges by increasing weight and keep adding the lightest edge to MST without causing cycles.

Reverse-Delete

MST, O(n^2). Start with whole graph and delete heaviest edges until minimally connected; correct MST via "cycle" property.

Selecting compatible intervals (3 bad, 1 good)

Greedy, O(n^2)

[X] Keep selecting shortest

[X] Keep selecting the one with the least conflicts

[X] Keep selecting the one that starts first

[Y] Keep selecting the one that ends the earliest

Fractional knapsack

Greedy, O(nB). Sort by value per weight, and keep adding as much as possible of each item without exceeding capacity.

LIS (longest increasing subsequence)

DP, O(n^2). Subproblem: OPT[i] = length of LIS that must end at A[i]. Recurrence: for OPT values before it, add 1 to the longest so far that is valid (< cur value)

0/1 Knapsack

DP, O(nB). Subproblem: OPT[i][j] = max value up to item i and capacity j. Recurrence: max of copying from above or subtracting capacity but getting new item

Edit distance

DP, O(nm). Subproblem: OPT[i][j] = edit distance from word1[1:i] to word2[1:j]. Recurrence: min of add 1 to up or left, or add 0 to up left if letters are the same, else add 1.

Max independent set (IS) in trees

DP, O(n). Subproblem: OPTin and OPTout = max if current is in MIS or not. Recurrence: OPTin = value + OPTout of children, OPTout = sum of max of OPTin and OPTout of children

DP DAG shortest path in graph

Shortest paths, O(m), negative allowed no cycles. Subproblem: OPT[v] = distance from s to v. Topo sort and then relax all edges.

Dijkstra's

Shortest paths, O(n^2). Positive only, cycles okay. For each unprocessed vertex, process each from lowest known distance and relax all edges.

Bellman-Ford

Shortest paths, O(mn). Negative allowed, cycles okay. Run n-1 times, relax all edges.

Floyd-Warshall

Shortest paths from to all pairs of vertices, DP, O(n^3). Negative allowed, cycles okay. Subproblem: OPT[u][v][r] = distance from u to v only allowed to use vertices 1:r. Recurrence: if using r, go from u to r then r to v, else use u to v only.

Ford-fulkerson

Maximum flows, O(mv). Construct flow network and allow "undo"s, stopping when no path from s to t.

Bipartite matching

Application of maximum flows, O(mv). Simply add s and t, all edge capacities = 1.

Minimum vertex cover (VC) of bipartite graphs

Application of maximum flows, O(mv). Add s and t but set middle edge capacities to infinity. Solution = L\S U RinS

VC (vertex cover) --> IS (independent set) reduction

Note: S is IS <=> V\S is a VC. Pass new input n-k for k.

3-SAT --> IS (independent set) reduction

Create triangles of clauses and add "conflict edges" between any x and !x pair in graph. Then find IS of those, answer is the ones you chose.

VC (vertex cover) --> DS (dominating set) reduction

Construct G' where each edge gets another "parallel" edge with a vertex in the middle. If you can finds DS of that, original graph had VC that size.

2-Approximation vertex cover

Approximation. Pick edges and add both endpoints to VC, removing edge, vertices, and all adjacent vertices. Repeat until none left.

2-Approximation load balancing

Approximation. Keep adding job to server with the current lowest load.