CS 277 TU Programming The Correctness of Prims Algorithm Questions

CS277 – Reading 4a
1
Reading
This reading is for CLRS, Introduction to Algorithms.
• Read pp 624 – 626 to introduce the minimum spanning tree (MST) problem and a generic
algorithm to solve it.
• Read pp 631 – 633 to review Kruskal’s algorithm.
– Kruskal’s algorithm relies on the disjoint-set data structure, which is described in section
21.1.
• Read pp 634 – 636 to review Prim’s algorithm and see an analysis of its runtime.
2
Questions
1. The following questions concern the construction of MSTs.
(a) How many edges are in a spanning tree of a connected, undirected graph G = (V, E)?
(b) Consider the predecessor table generated by BFS. Do the edges between vertices and their
predecessors form a tree? A spanning tree? A minimum spanning tree? Explain your
answers.
(c) Consider an incorrect MST algorithm where we simply added the edges from smallest to
largest weight until all vertices had been connected. Why is this algorithm incorrect?
(d) Is the MST problem defined for directed graphs? Explain your answer.
2. The following questions concern Kruskal’s algorithm.
(a) Kruskal’s only adds edges between vertices that are in separate sets. Why will this prevent
cycles from being added?
(b) Explain in your own words why Kruskal’s runtime can be expressed as O(E lg V ).
3. Consider the following psuedocode of Prim’s. This pseudocode is functionally the same as the
CLRS version, only a little more explicit.
1
1 Function Prim(G = (V, E), Adj, r):
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* G is an undirected, weighted graph; V, E are sets of vertices and
edges
/* Adj is an adjacency list of G where Adj[u] gives a list of u’s
neighbors
/* r is the root vertex
foreach u ∈ G.V do
u.added = f alse
u.key = ∞
u.π = NIL
r.key = 0
Initialize Q as priority queue containing all vertices
while Q is not empty do
u = Q.extract min()
u.added = true
foreach v ∈ Adj[u] do
if v.added == f alse then
v.π = u
Q.update key(v, w(u, v)) /* Sets v.key = w(u, v) and updates Q as
needed
return {(u, u.π) | u ∈ V \ {r}} /* MST is all (vertex, predecessor) edges
excluding the root node, which still has a NIL predecessor
*/
*/
*/
*/
*/
Prim’s runtime depends on what data structure we choose for the priority queue, as this will
affect the runtime of the initialize, extract minimum, and update key operations.
(a) Explain in your own words why Prim’s runtime can be expressed as O(E lg V ) if we use a
binary min heap as a priority queue.
(b) Say we used an unsorted array for the priority queue instead. Analyze the runtime of
Prim’s algorithm.
(c) Say we used a sorted array for the priority queue instead. Analyze the runtime of Prim’s
algorithm.
4. The following questions concern the correctness of Prim’s algorithm.
(a) Prim’s only adds edges that connect vertices already in the MST with vertices that haven’t
yet been added to the MST. Why will this prevent cycles from being added?
(b) Say we removed line 11 from the pseudocode of Prim’s given on pp 634. Would this
modified version of Prim’s still be correct? If yes, justify your answer. If no, give a
counterexample.
Page 2
CS277 – Reading 4b
1
Reading
This reading is for CLRS, Introduction to Algorithms.
• Read pp 643 – 646 to introduce the single source shortest path (SSSP, or simply SP) problem.
• Read pp 651 – 652 to review the Bellman-Ford algorithm.
• Read pp 648 – 649 and 658 – 659 to review Dijkstra’s algorithm and the relax edge subroutine.
• Read pp 661 – 662 to see an analysis of Dijkstra’s runtime.
2
Questions
1. The following questions concern the SP problem.
(a) Prove that Prim’s algorithm does not solve the SP problem, even for undirected graphs.
(b) Why is the SP problem not defined on graphs with negative weight cycles?
(c) What does CLRS mean when they say that shortest paths have an “optimal substructure”?
2. The following questions concern the Bellman-Ford algorithm.
(a) Briefly explain in your own words why the runtime of Bellman-Ford is O(V E).
(b) Why does the for loop on line 2 relax the edges in the graph V − 1 times? Why would the
algorithm potentially not find the correct shortest paths if it iterated less times?
(c) How could we improve the best case runtime of Bellman-Ford to be O(E) in certain cases?
What would be that certain case?
3. The following questions concern Dijkstra’s algorithm.
(a) Prove that Dijkstra’s algorithm can fail to find the shortest paths on a graph with negative
weight edges.
(b) Represent the runtime of Dijkstra’s algorithm with summations, then simplify to a single
Θ bound.
You may assume line 3 takes Θ(V ) time, and lines 5 and 8 take Θ(lg V ) time, as they
would if we were using a binary min heap.
(c) Why does Dijkstra’s have a better runtime than Bellman-Ford’s? Why would we ever use
Bellman-Ford’s?
(d) Explain the relax edge subroutine. What does it do? Why will it help find the shortest
paths?
1
4. Prim’s, Kruskal’s, and Dijkstra’s are greedy algorithms. What is a greedy algorithm? Do you
think all problems have greedy solutions? Why or why not?
Page 2