Week 2 (Greedy Algorithms) Flashcards
(19 cards)
How are greedy algorithms built?
Greedy algorithms build the solution step-by-step to create approximately optimal solutions rather than the optimal solution
What is the vertex cover set?
What is its brute force?
Given an undirected graph G=(V,E) of n vertices, find a set X of minimum size such that each edge has at least one endpoint in X.
Brute force 2^n . n^O(1)
What is Dijkstra’s algorithm? What is the greedy running time?
A directed graph G=(V,E) with n vertices and edge-lengths given by E → R^>=0. For each v ∈ V, find length of shortest s -> v path, where s is a fixed source vertex. #
Let S be set of explored vertices
For each u ∈ S we store distance of shortest u ↔ s path in dist(u)
Initialize S = {s} and dist(s) = 0
while S != V do
Select a vertex v ∉ S which minimizes temp-dist(v) = min(u,v)∈ E, u∈ S {dist(u) + length(u,v)}
Add v to S and set dist(v) = temp-dist(v)
end while
Total running time = O(mn)
How do we use Dijkstra’s for undirected graphs?
By converting an undirected edge into two directed edges
Why does Dijkstra fail for negative edges? Show the proof
Theorem: Consider the set S at any point during the algorithm. For each u -> S, the
quantity dist(u) stores the value of shortest s → u path.
Suppose there is a s -> v path P shorter than dist(v) that leaves S via the edge (x, y) for some x ∈ S, y ∉ S. This is a contradiction as the algorithm has already chosen dist(v) for the shortest path.
What are spanning trees?
Let G=(V,E) be an undirected, connected graph with n vertices. A subgraph T=(V’, E’) of G is said to be a spanning tree of G if:
- T has no cycles, V’ = V
- T has n-1 edges, |E’| = n - 1
- T is connected
What are minimum spanning trees?
Given an undirected, connected graph G, with edge-costs given by cost: E -> R^+, find a spanning tree such that ∑ e ∈ E’ cost(e) is minimised.
What is Prim’s algorithm and what its its running time?
Let S be set of explored vertices
Initialize S = {s} where s is any vertex
Initialize E’ = {}
while S != V do
Select a vertex v ∉ S which minimizes min
e=u-v, u∈S cost(e)
Add v to S and e to E↑
end while
Running time = O(mn)
What is the theorem for minimal spanning trees?
For any S c V, let e be the edge of minimum cost having one end-point in S and other endpoint in V\S. Every MST contains the edge e.
What is the proof for the correctness of Prims algorithm?
Suppose there is a MST T which doesn’t contain the edge e of minimum cost between s - v. By finding an edge e’ in T such that cost(e’) > cost(e), we get T’ = T - e’ + e. This spanning tree now has a smaller cost => contradiction since the shortest edges are chosen
What is Kruskal’s algorithm and what is its running time?
Order the edges of E as e1, e2, . . . , em in increasing order of costs
Initialize E↑ = ⇐ and i = 1
while i → m do
if adding ei to E↑ does not create a cycle then
Add ei to E↑
else
Do not add ei to E↑,
end if
Increase i by 1
end while
Running time = O(mn)
What is the correctness of Kruskal’s algorithm?
Suppose Kruskal’s algorithm adds edge v->w, with S being the set of all vertices to which v had a path. Since v ∈ S and w ∉ S, v-w is the cheapest edge with one end-point in S and the other end-point in V\S
What is the Reverse-Delete algorithm for minimal spanning trees?
Instead of adding edges in increasing order while avoiding cycles, the Reverse-Delete algorithm finds and deletes the most expensive edge in a cycle.
What is the Interval Scheduling Problem?
Given a set of n requests R = {Req(1),…,Req(n)}, each with a start and finish time, find a set C ⊆ R of requests such that |C| is minimised and no two requests from C conflict.
What is the greedy algorithm for the Interval Scheduling problem?
Let R = {Req(1), . . . , Req(n)} be set of all requests
Let C denote set of requests that we select
Initiate C = {}
while R != {} do
Find the request Req(i) ↓ R which has smallest finish time
Add Req(i) to C
Delete from R all requests that conflict with Req(i)
end while
What is the proof for the greedy Interval Scheduling problem?
Suppose another set OPT with more requests than C:
C = {Req(i1),…,Req(ik)} and OPT = {Req(j1),…,Req(jm)}
For each 1 <= ℓ <= k, we have Finish (iℓ) <= Finish(jℓ)
- Proof by induction on ℓ. Base case ℓ = 1
- Inductive step: Start(jℓ) >= Finish(jℓ-1) >= Finish(iℓ-1) so Req(jℓ) doesnt conflict with Req(iℓ-1) but our algorithm chose iℓ instead
Since m>k, OPT selected a request Req(jk+1)
- Start(jk+1) >= Finish(jk) >= Finish(ik)
- Contradiction, algorithm stopped after ik
What is the partitioning problem?
Partition a set of numbers into n pairs which minimises the maximum sum of a pair
What is the greedy algorithm for the partitioning problem?
Sort the numbers into increasing order and match yi and y2n+1-i for each 1 <= i <= n
What is the correctness for the greedy partitioning problem?
We claim that y1 can be paired with y2n
Suppose y1 is paired with yi and yj is paired with y2 such that y1 < yj and yi < y2n
Hence, y1 + yi < yj + y2n
Swap y1 and yj: so the pairs are now {y1, y2n} and {yi, yj}
y1 + y2n < yj + y2n because y1 < yj
yi + yj < yj + y2n because yi < y2n
