1. (a)
CSC 226 Practice Questions for Midterm
Consider the lazy version of Prim’s algorithm that incrementally builds up a set A of edges as its solution. Recall that this version maintains a priority queue of edges which might contain multiple edges incident to each vertex not currently spanned by A. Using big-O notation, what is the worst-case runtime of this algorithm in terms of |V | and |E|?
(b) Using big-O notation, what is the worst-case runtime complexity of Kruskal’s algo- rithm in terms of |V | and |E|?
(c) Complete the characterization of Eulerian graphs: A graph is Eulerian if it has at
most one nontrivial and all its vertices have (d) Is the graph below Hamiltonian?
.
(e) One implication of Kuratowski’s theorem is that the complete bipartite graph Kx,y is not planar. What are x and y? That is, select the smallest x and y such that Kx,y is not planar.
(d)
(e)
(f) How many faces does the graph below have?
(f)
2. Minimum Spanning Trees
(a) Suppose that Kruskal’s algorithm is run on the following weighted graph. List, in order, the sequence of edges added by the algorithm.
5
10
9
A
6
1G F
B7C3E
824
D
(b) Prove that Prim’s algorithm correctly finds a minimum spanning tree. You may assume that all edge weights are distinct. You may also rely on the fact that any edge satisfying the cut property is a safe edge.
Page 2
3. Union-Find
(a) Consider the following two lines of code:
1: If(Connected(2, 1) == 0) Union(2, 1) 2: If(Connected(3, 5) == 0) Union(3, 5)
Below is a forest of rooted trees. Fill in the values of the array id[].
id[] 012345
For the following, consider the Weighted Quick-Union version of Union-Find. Show how the forest looks after line 1, and draw the updated version of id[].
Show how the forest looks after line 2 (after already having run line 1), and draw the updated version of id[].
(b) For the forest of rooted trees shown below, consider the operation Find(4) when using Weighted Quick-Union with Path Compression. Draw the updated tree after this operation occurs.
305 214
81 293
56 74
Page 3
4. (6 points) Let G be a connected weighted graph with n vertices and which has non- negative edge weights. Describe a modification of the Bellman-Ford algorithm which identifies all single-source shortest paths of length k (for some fixed k < n) but which has a lower runtime than the standard Bellman-Ford algorithm. 5. (7 points) A traveling salesperson (“Traveler”) and taxicab driver (“Driver”) are having an argument about MST algorithms. Traveler says that Prim’s algorithm might return the wrong answer if any of the edge weights are negative, but Driver disagrees. Traveler proposes the following algorithm to find an MST T in a weighted graph G if there are any negative edges weights: First, find the minimum edge weight among the edges in G; call it w∗ (so, w∗ is the negative number of largest magnitude). Next, add |w∗| to all the edge weights, forming a new graph G′. Finally, run Prim’s algorithm on G′ and return the resulting MST T′. (a) Traveler and Driver don’t know if T′ is equal to T. Is it possible to conclude that T′ is equal to T? Explain your answer. (b) Driver claims that this whole exercise is a waste of time because Prim’s algorithm is correct even if there are negative edge weights. Is Driver right? Page 4 6. (8 points) Two graphs are below. For each graph, indicate whether or not it is 2- colorable. If any graph is not 2-colorable, show one odd cycle in the graph. First graph: Second graph: Page 5