Due: Wed, April 17th in class Late assignments will be penalized 20% per day.

Book Questions from Introduction to Algorithms - 4th ed.

21.1-2, 21.2-4, 21.2-5, 22.1-1 (8 points), 22.3-1 (7 points)

Hints:

21.1-2 - Consider the following graph

21.2-4 - Note that the running time of Kruskal’s algorithm is given by

But since |E| < |V²|, O(lg E) = O(lg V²) = O(2 lg V) = O(lg V) and hence O(E lg E) = O(E lg V). Note that the sorting step is the dominant term in the algorithm, so consider how the sorting step can be improved if the weights are integers in the range 1 to |V| (or 1 to W). What does this do to the overall asymptotic runtime of Kruskal’s algorithm?

21.2-5 - Note that the running time of Prim’s algorithm is given by

Since |E| can range from |V| to |V²|, the total runtime is the sum of both steps. The first part is a result of maintaining the priority queue (via a Fibonacci heap). If the edge weights are integers, consider using an array of linked-lists where the index of the head of each lists corresponds to the weights. Then extracting the minimum consists of simply scanning the array for the first non-empty list. Consider what the runtime of this priority queue implementation would be per vertex for weights in the range 1 to |V| and 1 to W. What does this do to the overall asymptotic runtime of Prim’s algorithm?

22.1-1 Complete the following tables showing the current shortest distance d and predecessor vertex π for each pass through the edges.

Then be sure to show the final relaxation check and state whether the final shortest distances are valid or not along with the shortest distance paths.

22.3-1 Complete the following tables showing the queue with current shortest distance keys as each vertex is removed from the queue.

Then show the final shortest distance paths.