3PART ONE * Lecture 1 (01/09)
Posted on: Monday, January 28, 2013
Topics: Stable Matching
Reading: class handout * Lecture 2 (01/14)
Posted on: Thursday, January 24, 2013
Topics: Graph Representation, BFS, DFS
Reading: CLRS (Sections 22.1, 22.2, 22.3), KT (3.2, 3.3)

Notes:
2 possible representations of a graph 1. Adjacency Matrix-used for dense graphs (V2 memory space) a. Aij=1 if edge exists between I and J but 0 if not 2. Adjacency List- Used for sparse graphs (V+E memory space or V+2E for undirected) b. Array adj of |V| lists, one for each vertex. c. Adj[u] contains all vertices adjacent (or reachable by one edge) to u
Breadth First Search(G,s) BFS.G; s/
1 for each vertex u in G.V –{s}
2 u.color = WHITE
3 u.disc =∞
4 u.parent= NIL
5 s.color = GRAY
6 s.disc = 0
7 s.parent= NIL
8 Q = ∅;
9 ENQUEUE(Q,s)
10 while Q ≠ ∅
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color == WHITE
14 v.color = GRAY
15 v.disc = u.disc + 1
16 v.parent = u
17 ENQUEUE(Q,v)
18 u.color = BLACK

White means not discovered yet, grey mean discovered but not finished, black means finished.
Run time O(V+E)
BFS gives shortest path from s to every vertex
Lemma: x in Li and Y in Lj and edge (x,y) exists Then |i-j| less than or equal to 1

Depth First search
Properties: 1) v is a descendenant of u iff v if discovered when u is gray
2) Parenthesis theorem, u and v in V. either discovery and finish times are disjoint (u nor v are descendents of each other) or one is discovered after and finished before the other (u is a descendent of v or vice versa)

White path theorem In a depth-first forest, vertex v is a descendant of u if and only if at the u is discovered there is a path from u to v consisting entirely of white vertices.

Edge classification Tree edge: edges present in depth first tree Back edge: connects descendant to ancestor in tree (not shown) Forward edges : connects to a descendant not in tree Cross edges : all other edges

DFS(G) O(V+E)
1 for each vertex u in G.V
2 u.color = WHITE
3 u.parents = NIL
4 time = 0
5 for each vertex u in G.V
6 if u.color == WHITE
7 DFS-VISIT.G; u/
DFS-VISIT(G,u)
1 time = time C 1 // white vertex u has just been discovered
2 u.disc = time
3 u.color = GRAY
4 for each v in G.Adj[u] // explore edge (u,v)
5 if v.color == WHITE
6 v.parent = u
7 DFS-VISIT(G,v)
8 u.color = BLACK // blacken u; it is finished
9 time = time + 1
10 u.finished = time

if edge u,v is traversed, and v is white, tree edge and v is gray, back edge and v is black, cross edge or forward edge * Lecture 3 (01/16)
Posted on: Thursday, January 24, 2013
Topics: DFS, Homework 1 out
Reading: CLRS (22.3) * Lecture 4 (01/23)
Posted on: Thursday, January 24, 2013
Topics: Topological Sort, Testing Bipartiteness, Strongly Connected Components
Reading: CLRS (22.4, 22.5), KT (3.4)
Strongly Connected Components
1.Call DFS(G) to compute finishing times for u.f for each vertex u
2. compute Gt, which is the graph with all edges reversed.
3. Call DFS(Gt) but in main loop process vertices in order of decreasing finishing time as computed in part 1
4. output the vertices of each tree in the depth first forest formed in step 3 as a separate SCC

Component graph: just a graph of with each vertex representing an SCC, must be a DAG

Topological Sort O(V+E)
-performed on directed acyclic graph
Linear ordering of all its vertices such that if G contains an edge (u,v) then u appears before v in the order. 1. call DFS(G) to compute finishing times v.f for each vertex v 2. as each vertex is finished insert it onto the front of a linked list 3. return the linked list of vertices 4. Lecture 5 (01/28)
Posted on: Monday, January 28, 2013
Topics: Strongly Connected Components, Activity Selection
Reading: CLRS (22.5, 16.1), KT (4.1)
Scheduling Probelem
Set of n activities which can be served only one at a time, each with start time s and finish time f
Selecct a maximum-size subset of mutually compatible activities (meaning no overlap)

GREEDY ALGORITHM
Note that putting the job with the earliest finish time allows for the most amount of jobs to follow, because it allows the machine to have the most possible time to get to other jobs
Take job with lowest finish time, then reduce set to all job that don’t overlap, then choose lowest finishing time, recursively. * Lecture 6 (01/30)
Posted on: Wednesday, January 30, 2013
Topics: Activity Selection, Coloring Interval Graphs, Scheduling
Reading: CLRS (16.1, 16.2), KT (4.1, 4.2) * Lecture 07 (02/04)
Posted on: Wednesday, February 6, 2013
Topics: Minimizing Maximum Lateness, Sorting (Insertion Sort, Merge Sort, Quick Sort)
Reading: CLRS (Chp 2, 7.1, 7.2), KT (4.2)
Insertion sort
Starting from the second element as key value, while the key value taken is less than the element in the array corresponding to the counter (running down from the index of the key value, initially 2 for first run through), move the value in the array up and then place the key in the counter + 1 space. Recursive biatch

Merge sort 1. Break array in half 2. Call merge sort on left half 3. Call merge sort on right half 4. Call Merge
Merge
1. Take subarrays of input, left and right 2. Compare elements by element and put back in array in right place a. If comparison, easy
Run time = O(n lg n)
Recurrence equations: T(n) = T(f(n)) + O(g(n))

Bubble sort 1. Have a counter that starts one away from the end of the array i and one that starts at the end of the array j 2. Compare element j with element j-1 until j =i a. Change elements if j is less than j-1

Inversions: elements in array out of order, i < j, but A[i] > A[j]

Quick Sort: 1. Find partition or pivot in array 2. Call quicksort on subarray to right and left of pivot

Partition 1. Take last element of input array, key 2. Compare element to key, if less than put in left subarray, if greater put in right subarray
Worst case run time : O(n2) * Lecture 8 (02/06)
Topics: Master Theorem, Selection, Counting Inversions
Reading: CLRS (4.5, 9.1, 9.3), KT (5.3), handout for Simplified Master Theorem

THE MASTER THEOREM
For recurrences of the form T(n) = aT(n/b) + f(n) 1. If f(n)=O(nlog(b) a−ϵ) for some constant ϵ>0, then T(n)=Θ(nlog(b)a) 2. If f(n)=Θ(nlog(b)a), then T(n)=Θ(nlog(b)a lg n) 3. If f(n)=Ω(nlog(b)a+ϵ) for some constant ϵ>0, and if af(n/b)≤cf(n) for some constant c<1 and all sufficiently large n, then T(n)=Θ(f(n))

PART TWO * Lecture 9 (02/11)
Posted on: Monday, February 11, 2013

Topics: Heaps, Lower bound on sorting Reading: CLRS (Chp. 6, 8.1)

Heaps:
Heap_size is the number of elements in the heap array to be included in the heap, while length is the number of elements in the heap array.
Parent: , right child: 2i+1, left child: 2i
Heap property: Max heap prop: A[parent(i)]>A[i]
MAX-HEAPIFY(A,i) O(lg n) or O(h)
1 l LEFT(i) /
2 r RIGHT(i) /
3 if l ≤ A.heap-size and A[l] > A[i]
4 largest l
5 else largest i
6 if r ≤ A.heap-size and A[r] > A[largest]
7 largest r
8 if largest ≠ i
9 exchange A[i] with A[largest]
10 MAX-HEAPIFY(A, largest)

Checks node in question, if either of its children are larger than it, swap the original node with the larger of its children and run max heapify on the subtree that the original node was pushed down to. Maintains heap property.

BUILD-MAX-HEAP.A/
1 A.heap-size <- A.length
2 for i <- downto 1
3 MAX-HEAPIFy(A, i)

every node indexed at an index greater than must be a leaf with no children.
Upper bound: O(n lg n)
But since the heights range from 0 to lg n and the number of nodes at each height is , the run time is

HEAPSORT(A) O(n lg n)
1 BUILD-MAX-HEAP(A)
2 for i <- A.length down to 2
3 exchange A[1] with A[i]
4 A.heap-size <- A.heap-size-1
5 MAX-HEAPIFY(A, 1)

Builds a max heap, then at each iteration, puts the maximum at the index to be removed from the heap size (so a max heap is sorted in ascending order by placing the greatest numbers at the end of the array), then max heapifies all indices less than the exchanged one, until there is only one element left which must be the smallest.

Heap Maximum(A) O(1)
Return A[1]

HEAP-EXTRACT-MAX.A O(lg n)
1 if A.heap-size < 1
2 error “heap underflow”
3 max <- A[1]
4 A[1] <- A[A.heap-size]
5 A.heap-size <- A.heap-size-1
6 MAX-HEAPIFY(A, 1)
7 return max

Saves the value of the max, places the last node in the heap at the top of the heap, then maintains heap property.

HEAP-INCREASE-KEY(A, i, key) O(lg n)
1 if key < A[i]
2 error “new key is smaller than current key”
3 A[i] <- key
4 while i > 1 and A[PARENT(i)] < A[i]
5 exchange A[i] with A[PARENT(i)]
6 i <- PARENT(i)

Only increase the value at i to key if key is greater than the current value there. Then while we haven’t hit the top of the heap and the parent is still less than the new value inserted, exchange the new value with its parent and set i to the value of its parent.

MAX-HEAP-INSERT(A, key) O(lg n)
1 A.heap-size <- A.heap-size - 1
2 A[A.heap-size] <- 1
3 HEAP-INCREASE-KEY[A, A.heap-size, key]

* Lecture 10 (02/13) * 
Posted on: Wednesday, February 13, 2013 * 

Topics: Lower bound on Sorting, Counting Sort, Radix Sort, Randomized Quick Sort * Reading: CLRS (8.1, 8.2, 8.3, 7.3, 7.4)


 Randomized Quicksort: Instead of selecting r as the pivot, select an element at random from A[p…r] Expected run time: Xij=1 if elements i and j are compared X = total comparisons = E[X] = E[]= P(Xij=1) = P(element i is chosen as pivot) + P(element j is chosen as pivot) There are j-i+1 elements in range ij, so Probability of any element being chosen as pivot is 1/(j-i+1), so probability of either being chosen is 2/(j-i+1). So the expected run time is O(n lg n)

Lower Bound on Sorting: Any comparison sort algorithm requires Ω(n lg n) comparisons in the worst case COUNTING-SORT(A,B, k) O(n) if k < n… k is largest integer
1 let C[0… k] be a new array
2 for i <- 0 to k
3 C[i] <- 0
4 for j <- 1 to A.length
5 C[A[j] ] <- C[A[j ] + 1
6 // C[i] now contains the number of elements equal to i .
7 for i <- 1 to k
8 C[i]_<- C[i] + C[i-1]
9 // C[i] now contains the number of elements less than or equal to i .
10 for j <-A.length down to 1
11 B[C[A[j]]] <- A[j ] 12 C[A[j]] <- C[A[j]]-1 Counts the number of elements less than one to determine its sorted place RADIX-SORT(A,d) O(d(n+k))
1 for i <- 1 to d 2 use a stable sort to sort array A on digit i Sort the least significant digits (by shifting entire numbers) up to the most significant

* Lecture 11 (02/18) * 
Posted on: Wednesday, February 20, 2013

Topics: Dijkstra's shortest path algorithm, Minimum spanning trees * Reading: CLRS (24.2, 24.3, 23.1, 23.2), KT (4.4, 4.5)




Minimum Spanning Tree Algorithms
A minimum spanning tree must span every vertex in the graph and have the smallest sum of edge weights of any spanning tree

MST-KRUSKAL(G,w) O(E lg V)
1 A <-Ø
2 for each vertex v ∈G.V
3 MAKE-SET(v)
4 sort the edges of G.E into nondecreasing order by weight w
5 for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight
6 if FIND-SET(u) ≠ FIND-SET(v)
7 A <- A ∪ {(u,v)}
8 UNION(u,v)
9 return A

Each edge is an individual “set” to begin with. Since edges are taking in nondecreasing order, if this edge connects two sets that are not the same, then this edge must be the smallest edge to connect these sets so add it to the min span tree

MST-PRIM(G,w,r) O(E lg V)
1 for each u ∈ G.V
2 u.key <-
3 u.parent <-NIL
4 r.key <- 0
5 Q <- G.V
6 while Q ≠ Ø;
7 u <- EXTRACT-MIN(Q)
8 for each vertex v ∈ G.Adj[u]
9 if v ∈Q and w(u,v) < v.key
10 v.parent <- u
11 v.key <- w(u,v)

Set all keys to infinity for all nodes but the starting point, then remove starting node at the first iteration and update the keys of all adjacent vertices, then go to the smallest of those and then update adjacent vertices and remove the smallest, repeat.

Shortest Path from source vertex algorithms

Shortest path properties
1. Subpaths of shortest paths are also shortest paths
2. Negative weight cycles cause elements on the negative weight cycle (and paths reachable from this cycle) to have a distance of negative infinity
3. Triangular inequality: For any edge (u,v) ∈ G.E, we have d(s,v) ≤ d(s,u) + w(u,v)
4. Upper bound property: We always have v.d ≥ d(s, v) for all vertices in V and once v.d achieves the value d(s,v), it never changes.
5. When there is no path to a vertex its distance is infinity
6. If the shortest path to v is a path from s to u then the edge u to v and u.d = d(s,u) prior to relaxing edge (u,v ) then v.d = d(s, v) at all times after the edge is relaxed.
7. Edges on a path are relaxed in order (not necessarily one after another, but if s goes to t then to u then to v, it relaxes edges (s,t) then (t,u) then (u,v).
8. Once v.d = d(s,v) for all vertices in V , the predecessor subgraph is a shortest-paths tree rooted at s.

* DIJKSTRA(G,W, s) O( VlgV + E) with fibonnaci heap
1 INITIALIZE-SINGLE-SOURCE(G,s) * 2 S <-Ø * 3 Q <- G.V * 4 while Q ≠ Ø ; * 5 u <- EXTRACT-MIN(Q) * 6 S <- S ∪ {u} * 7 for each vertex v ∈ G.Adj[u] * 8 RELAX(u, v, w) *

* DAG-SHORTEST-PATHS(G, w, s) O(V+E) * 1 topologically sort the vertices of G * 2 INITIALIZE-SINGLE-SOURCE.G; s/ * 3 for each vertex u, taken in topologically sorted order * 4 for each vertex v ∈ G.Adj[u] * 5 RELAX(u, v, w)

* Lecture 12 (02/20)
Posted on: Wednesday, February 20, 2013

Topics: Minimum Spanning Trees, Huffman Coding * Reading: CLRS (Chp 23, 16.3), KT (4.4, 4.5, 4.8) * 


Huffman Coding * Prefix coding: no encoding is a prefix of another encoding (allows variable length encoding) *
HUFFMAN(C )
1 n <- |C|
2 Q <- C
3 for i <-1 to n- 1
4 allocate a new node z
5 ´ z.left <- x <- EXTRACT-MIN(Q)
6 ´ z.right <- y <- EXTRACT-MIN(Q)
7 ´ z.freq <- x.freq + y.freq
8 INSERT(Q,z) * 9 return EXTRACT-MIN.Q/ // return the root of the tree

* Lecture 15 (03/11)
Posted on: Monday, March 11, 2013

Topics: Dynamic Programming (Computing powers of 2, Weighted Interval Scheduling) * Readings: KT (6.1, 6.2)




* Lecture 16 (03/13)
Posted on: Wednesday, March 13, 2013

Topics: Dynamic Programming (Knapsack, Longest Common Subsequence) * Readings: CLRS (15.4), KT (6.4) * 4 steps: * 1. Characterize the structure of an optimal solution. * 2. Recursively define the value of an optimal solution. * 3. Compute the value of an optimal solution, typically in a bottom-up fashion. * 4. Construct an optimal solution from computed information. Common subproblems
Finding the right subproblem takes creativity and experimentation. But there are a few standard choices that seem to arise repeatedly in dynamic programming.
i. The input is x1, x2,…, xn and a subproblem is x1, x2,… xi.
The number of subproblems is therefore linear. ii. The input is x1,…, xn, and y1,…,ym. A subproblem is x1,… ,xi and y1… yj.
The number of subproblems is O(mn). iii. The input is x1…xn and a subproblem is xi,xi+1,…,xj .
The number of subproblems is O(n2). iv. The input is a rooted tree. A subproblem is a rooted subtree. Edit distance example: Example of comparing two different arrays of length n and m Transform String A (array of length n) in B (length m) by the minimum number of transformation (insert, delete, or replace: Cost = 1, else 0) Goal: Minimize total cost of transforming A into B T[i,j] = Min cost to transform A[1…i] into B[1…j] T[i,j] = Min (Cd+T[i-1,j], Ci+T[i,j+1], if A[i] = B[j] then T[i-1,j-1], else T[i-1,j-1]+Cr) Longest Increasing Subsequence: Example of a sequence dyn prog prob Find the longest (not necessarily contiguous subsequence) of increasing numbers L(i) = longest subsequence of all elements up to i L(j) = max for all i<j of { if A[i] < A[j], L[i]+1, else L[i]} Balanced Partition Problem: Similar to knapsack problem, n integers ranging from 0 to k. Partition subsequences so that the difference between the sum of the two is minimized THINK OF EVERYTHING AS AN ARRAY

* Lecture 17 (03/18)
Posted on: Monday, March 18, 2013

Topics: Dynamic Programming (Edit Distance, Matrix Multiplication) * Readings: DPV (6.3), CLRS (15.2, 15.3)

* Lecture 18 (03/20)
Posted on: Wednesday, March 20, 2013
Topics: Network Flows
Readings: CLRS (26.1, 26.2), KT (7.1)

Flow network: G (V,E) is a directed graph in which each edge (u,v) in E has a nonnegative capacity c(u,v) ≥ 0. If (u,v) in E, there is no (v, u) in E, capacity of any edge not in E is 0 and no self loops. Graph is connected and each vertex has at least one incoming edge, so |E| ≥ |V|-1

For each vertex v in V, there exists a path from source (s) to v to sink (t) Flow: capacity constraint: For all u, v in V, the flow on the edge from u to v is greater than or equal to 0 and less than or equal to the capacity of the edge (u,v) Flow conservation: for each vertex v in V- {s,t}

value of flow: anti parallel edges: edges from u to v and v to u. take v to u and create a new vertex with edge from v with same capacity as (v,u) and edge to u with same capacity as (v,u) multi sinks and sources: edges from super source, S, to all s with capacity infinity. Same for T, but edges to it instead Ford Fulkerson: initialize all f(u,v) to 0. Find an augmenting path from s to t, find residual network and repeat until no more augmenting paths exist Residual network: c(u,v) in Gf is c(u,v) from previous residual network – flow pushed through this edges on augmenting path. add this flow to the reverse edge

2|E| ≥ |Ef| Augmenting path: Increase flow on each edge in the residual graph by the minimum capacity edge on the path Cut: partition of V into S and T with s in S and t in T f(S,T) = net flow across cut= c(S,T) = capacity of S-T cut = Max flow min cut thm
If f is a flow in a flow network G (V,E) with source s and sink t , then the following conditions are equivalent:
1. f is a maximum flow in G.
2. The residual network Gf contains no augmenting paths. 3. |f | = c(S,T) for some cut (S,T) of G. Edmond karp alg: ford Fulkerson using BFS to find augmenting path. runs in O(VE2)

* Lecture 19 (03/25)
Posted on: Tuesday, March 26, 2013
Topics: Max Flow-Min Cut Theorem, Bipartite Matching
Readings: CLRS (26.2, 26.3), KT (7.1,7.2,7.5)
Posted by: Rajiv Gandhi
Posted to: CIS 320-001 2013A. Intro To Algorithms

Maximum bipartite matching:
Given an undirected graph G (V,E), a matching is a subset of edges M ⊆ E such that for all vertices v in V , at most one edge of M is incident on v. We say that a vertex v in V is matched by the matching M if some edge in M is incident on v; otherwise, v is unmatched. A maximum matching is a matching of maximum cardinality, that is, a matching M such that for any matching M’, we have |M| ≥ |M’|.

Corresponding flow network: Partition G into L and R, directed edges in G’ are undirected edges from L to R in G, add s with edges to all vertices in L and edges from all vertices in R to added t. each edge has unit capacity.
|E| ≥ |V|/2 so |E| ≤|E’|=|E| + |V| ≤ 3|E|

Run FF on corresponding flow network, |M| = |f|

* Lecture 20 (03/27)
Posted on: Wednesday, March 27, 2013
Topics: Bipartite Matching, Karger's min-cut algorithm, Image Segmentation
Readings: class handout, CLRS (26.3), KT (7.5, 7.10)
Posted by: Rajiv Gandhi
Posted to: CIS 320-001 2013A. Intro To Algorithms

Karger’s min cut alg: contract edge, merge vertices, reattach all edges to merged vertex.

Image segmentation: Graph G of pixels, each pixel has an undirected edge to each of its neighbors. Determine what is in foreground and what is in background. Each pixel i has probability ai that it belongs to foreground, bi that is belongs to background. And for each pair of neighboring pixels ij, there is a penalty pij for putting one in foreground and another in background. Partition pixels into A and B

Max or we can say
Minimize
Alg: create supersource and supersink, edge from s to all vertices with capacity ai and edge from all vertices to supersink t with capacity bi. Between each pair of neighboring vertices is an edge with capacity pij.

Three types of edges that cross cut: from s to a vertex in B which contributes ai, from a vertex in S to t which contributes bi, and an edge between neighbors pij

Lecture 21 (04/01)
Posted on: Tuesday, April 2, 2013
Topics: Image Segmentation, NP-Completeness
Readings: CLRS (34.1 - 34.3), KT (7.10)
Polynomial time verification: select certificate (specific instance of problem) and decide if this certificate is in fact a solution to the problem

A language is NP complete if it can is in NP (has a polynomial time verifier) and can be reduced from another NP problem to the one described

Polynomial time reduction: convert this problem into an instance of another NP complete problem (an instance of the problem will have a solution if and only if its reduction does as well)

PROBLEMS~
Packing: You have some objects, and you want to choose at least of them. You need to deal with conflicts between objects (you can't choose all of them).
Set Packing: given m elements, S is a set of subsets of the universe, find a subset of S that is pairwise disjoint
Independent Set: find maximum set of non-adjacent vertices
Clique: find subset of vertices that there is an edge between each pair of vertices

Covering: You have some objects, and you want to choose at most of them. The constraint is that these objects together should achieve some overall goal.
Set Cover: set of m elements, set S of n sets whose union is all m element, find subset of S whose union is all m elements
Vertex Cover: subset of vertices such that for all edges at least one vertex of each edge is in the vertex cover

Partitioning: You want to search over all ways to divide your collection of objects into non-overlapping subsets.
Partition: Partition S into S1 and S2 such that the sum of each subset is equivalent
3D Matching (Can also think of as a packing problem + a covering problem at the same time): 3 sets X, Y, Z and a set of triplets (x, y, z). Find maximum subset of triplets such that there is no overlap
Graph Coloring (Want to partition with conflicts: conflicting objects can't go in the same set): color vertices such that no to adjacent vertices have the same color

Sequencing: You want to search over all permutations of a sequence.
Hamiltonian Path/Cycle: path/cycle that goes through every vertex exactly once
Traveling Salesman: Hamiltonian cycle that is less than weight k

Numerical Problems
Subset Sum: find a subset of S that sums to t
Knapsack: given a set of items and a bag with capacity C, find subset of items with maximum value with sum of weights less than C

General Purpose: Your problem doesn't fall into the above classes, or you're not sure.
3 SAT:

* Lecture 23 (04/08)
Posted on: Monday, April 8, 2013
Topics: NP-completeness, Reductions
Readings: CLRS (34.3, 34.4, 34.5)

* Lecture 24 (04/10)
Posted on: Wednesday, April 10, 2013
Topics: NP-complete Reductions
Reading: KT (8.6, 8.7, 8.8)
Posted by: Rajiv Gandhi
Posted to: CIS 320-001 2013A. Intro To Algorithms

* Lecture 25 (04/15)
Posted on: Monday, April 15, 2013
Topics: Bellman-Ford, Floyd-Warshall
Readings: KT (6.8), CLRS (24.1, 25.2)
Posted by: Rajiv Gandhi Posted to: CIS 320-001 2013A. Intro To Algorithms Bellman ford: initialize distance from source to source as 0 and from source to all others as infinity, relax all edges on graph V-1 times, at end check whether negative weight cycle exists by checking that for each edge (u,v) , d[u] + w ≥ d[v] Runs in O(VE) Floyd Warshall: let dij(k) be the minimum distance from i to j for which all intermediate vertices are in (1,2,…,k), set dij(0) as wij For k = 1 to n, for i=1 to n, for j=1 to n dij(k)=min(dij(k-1), dik(k-1)+dkj(k-1))

Runs in O(V3)

* Lecture 26 (04/17)
Posted on: Thursday, April 18, 2013
Topics: Approximation Algorithms (Vertex Cover, k-Center, TSP)
Readings: CLRS (35.1, 35.2), class handout
Posted by: Rajiv Gandhi
Posted to: CIS 320-001 2013A. Intro To Algorithms

Vertex cover approximation: no more than 2*Opt
Select an arbitrary edge, add u and v to return set, remove that edge and all edges incident on u or v, repeat until there are no edges left.

Proof of 2*OPT
Let A denote the set of edges selected arbitrarily, to cover these edges in any other vertex cover, specifically C*, at least one end point of the edges in A must be selected and no two edges in A are covered by the same end point in C* by construction of the algorithm

So |C*| ≥ |A|

Since we remove all incident edges, we never select an edge with an end point already in C,
SO |C| = 2|A|

Thus: |C|=2|A|≤2|C*|

TSP approximation:
Select a vertex to be root, find minimum spanning tree, order vertices in preorder walk of MST, return that ordered list

2 time approximation for TSP proof with triangle inequality
The weight of the MST must be less than or equal to the weight of the minimum ham cycle and since every edge in the MST is traversed twice, the weight of the solution from this algorithm must be 2*weight of MST, so the approximation is at most 2*optimal

* Lecture 27 (04/22)
Posted on: Monday, April 22, 2013
Topics: Approximation Algorithms (TSP, Set Cover)
Readings: class handout
Posted by: Rajiv Gandhi
Posted to: CIS 320-001 2013A. Intro To Algorithms