CS6033 Homework Assignment 10∗
1. For the graph above, run Prim’s algorithm. Start at node a. Whenever there is a choice of nodes, always use alphabetic ordering. Show the order the vertex are removed from Q, and draw the minimum spanning tree T for the graph.
2. Perform the following operations using the Union-Find where you start from the singleton sets {1}, ..., {9}. Use path compression. Provide your answer after every step.
• UNION(1,2) • UNION(3,4) • UNION(5,6) • UNION(7,8) • UNION(1,4) • UNION(5,7) • UNION(2,9) • UNION(5,1) • FIND-SET(7)
∗Many of these questions came from outside sources.
3. What is the optimal revenue for a rod of length 5? Use the following table: lengthi 1 2 3 4 5
pricepi 2 5 8 9 10
4. In Union-Find without using path-compression, perform the following
• For any node in the tree, determine the minimum number of nodes in the subtree rooted at that node
• Determine an upper bound on the height of a tree.1 Prove your bound is correct
• Prove that the maximum time to compute FIND-SET is O(log n) where n is the number
of MAKE-SET operations.
5. Suppose that all edge weights in a graph are integers in the range from 1 to |V |. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W ?
6. Suppose you have n rooms that you would like to connect in a communication network in one of the dormitories of Flash University. You have modeled the problem using a connected, undirected graph, G, where each of the n vertices in G is a room and each of the m edges in G is a possible connection that you can form by running a cable between the rooms represented by the end vertices of that edge. In this case, however, there are only two kinds of cables that you may possibly use, a 12-foot cable, which costs $10 and is sufficient to connect some pairs of rooms, and a 50-foot cable, which costs $30 and can be used to connect pairs of rooms that are farther apart.
Describe how you can turn this problem into a graph.
Describe an algorithm for finding a minimum-cost spanning tree for G in O(n + m) time.
7. Suppose Joseph Kruskal had an evil twin, named Peter, who designed an algorithm that takes the exact opposite approach from his brother’s algorithm for finding an MST in an undirected, weighted, connected graph, G. Also, for the sake of simplicity, suppose the edges of G have distinct weights. Peter’s algorithm is as follows: consider the edges of G by decreasing weights. For each edge, e, in this order, if the removal of e from G would not disconnect G, then remove e from G. Peter claims that the graph that remains at the end of his algorithm is a minimum spanning tree. Prove or disprove Peter’s claim.
8. Does Prim’s algorithm work if we allow negative edge weights? Prove or disprove.
9. Show, by means of a counterexample, that the following “greedy” strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be pi/i, that is, its value per inch. The greedy strategy for a rod of length n cuts off a first piece of length i, where 1 ≤ i ≤ n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n − i.
1Find the tightest bound you can prove.
10. Consider a modification of the rod-cutting problem in which, in addition to a price pi for each rod, each cut incurs a fixed cost of c. The revenue associated with a solution is now the sum of the prices of the pieces minus the costs of making the cuts. Your algorithm should not only value but the actual solution, too.
Provide a recurrence relation that would calculate both the optimal revenue and the optimal cuts.
Using your recurrence relation, give a dynamic-programming algorithm to solve this modified problem.
11. Consider a road of M miles. The task is to designate lots on which to build houses on the road such that revenue is maximized. The possible sites for the house are given by number x1 < x2 < ... < xn−1 < xn, specifying positions in miles of the center of each lot measured from one end of the road. If we place a house at lot i (where the center of the lot is in position xi), we receive a revenue of ri > 0. There is a restriction that no two houses (as measured by the center of each lot) can be placed within t miles or less than it.
As a first step in solving this problem, create the recurrence relation that returns the maximum revenue possible while satisfying that not two houses can be placed within t miles or less.
What size table do you need to store the subproblems using big-Oh notation?
Create an example of where n = 3, and show how your algorithm works on this example.
12. (3 bonus points) Think of a good exam question for the topics in this lecture.
