CS 163, Spring 2012, Homework 4, due Thursday, May 3

  1. Draw an undirected graph with eight vertices, for which Borůvka's algorithm uses three rounds to find the minimum spanning tree. Is this possible for graphs with seven vertices? Why or why not?

  2. Suppose that a three-way election is held between three candidates named Sarkozy, Merkel, and Putin. Among the voters,

    45% prefer Sarkozy first, Merkel second, and Putin last,
    35% prefer Putin first, Merkel second, and Sarkozy last, and
    20% prefer Merkel first, Putin second, and Sarkozy last.
    1. Who would win in an election using the Borda count?

    2. Who would win in an election using instant runoff?

    3. Who would win in an election using the Schulze widest-path system?

    4. Is there a Condorcet winner? If so, who is it? If not, why not?

  3. List the edges of the minimum spanning tree for the graph shown below, in the order that Kruskal's algorithm would add them to the tree.

  4. What is the running time for each of the three algorithms, Prim-Dijkstra-Jarnik, Borůvka, and Kruskal, when used to build a maze from a k-by-k grid of squares? For Prim-Dijkstra-Jarnik, use the analysis for the variant of the algorithm that uses binary heaps, and for Kruskal's algorithm, assume that the sorting stage of the algorithm is done using a comparison sorting algorithm. Express your answers in O-notation, as a function of k.