CS161-Homework 7 Solved

Consider the graph G below.

 

(a)    What MST does Prim’s algorithm return? In what order does Prim’s algorithm add edges to the MST when started from vertex C?

(b)   What MST does Kruskal’s algorithm return? In what order does Kruskal’s algorithm add edges to the MST?



 
 
 

2. At a Thanksgiving dinner, there are n food items f0,...,fn−1. Each food item has a tastiness ti 0 (measured in units of deliciousness per ounce) and a quantity qi 0 (measured in ounces). There are qi ounces of food fi available to you, and for any real number x ∈ [0,qi], the total deliciousness that you derive from eating x ounces of food fi is x · ti. (Notice that x here doesn’t have to be an integer).

Unfortunately, you only have capacity for Q ounces of food in your belly, and you would like to maximize deliciousness subject to this constraint. Assume that there is more food than you can possibly eat:

Pi qi ≥ Q.

(a) Design a greedy algorithm which takes as input the tuples (fi,ti,qi), and outputs tuples (fi,xi) so that 0 ≤ xi ≤ qi, Pi xi ≤ Q, and Pi xiti is as large as possible. Your algorithm should take time O(nlog(n)).

 
(b) Fill in the inductive step below to prove that your algorithm is correct.

•   Inductive hypothesis: After making the t’th greedy choice, there is an optimal solution that extends the solution that the algorithm has constructed so far.

•   Base case: Any optimal solution extends the empty solution, so the inductive hypothesis holds for t = 0.

• Inductive step: (you fill in)
• Conclusion: At the end of the algorithm, the algorithm returns an set S∗ of tuples (fi,xi) so that Pi xi = Q. Thus, there is no solution extending S∗ other than S∗ itself. Thus, the inductive hypothesis implies that S∗ is optimal.

 

1. Consider the problem of making change. Suppose that coins come in denominations P = {p0,...,pm} cents (for example, in the US, this would be P = {1,5,10,25}, corresponding to pennies, nickels, dimes, and quarters). Given n cents (where n is a non-negative integer), you would like to find the way to represent n using the fewest coins possible. For example, in the US system, 55 cents is minimally represented using three coins, two quarters and a nickel.

(a) Suppose that the denominations are P = {1,10,25} (aka, the US ran out of nickels). Your friend uses the following greedy strategy for making change:

 

Algorithm 1: makeChange(n) Input: n and P
 

 

Your friend acknowledges that this won’t work for general P (for example if P = {2} then we simply can’t make any odd n), but claims that for this particular P it does work. That is, your friend claims that this algorithm will always return a way to make n out of the denominations in P with the fewest coins possible.

Is your friend correct for P = {1,10,25}?

(b) Your friend says that additionally their algorithm should work for any P of the form P = {1,2,4,8,...,2s}.

Is your friend correct for P = {1,2,4,...,2s}?

2. On Thanksgiving day, you arrive on an island with n turkeys. You’ve already had thanksgiving dinner (and maybe you prefer tofurkey anyway), so you don’t want to eat the turkeys; but you do want to wish them all a Happy Thanksgiving. However, the turkeys each have very different sleep schedules. Turkey i is awake only in a single closed interval [ai,bi]. Your plan is to stand in the center of the island and say loudly “Happy Thanksgiving!” at certain times t1,...,tm. Any turkey who is awake at one of the times tj will hear the message. It’s okay if a turkey hears the message more than once, but you want to be sure that every turkey hears the message at least once.

(a)    Design a greedy algorithm which takes as input the list of intervals [ai,bi] and outputs a list of times t1,...,tm so that m is as small as possible and so that every turkey hears the message at least once. Your algorithm should run in time O(nlog(n)).

(b)   Prove that your algorithm is correct.

3. Let G be a connected weighted undirected graph. In class, we defined a minimum spanning tree of G as a spanning tree T of G which minimizes the quantity

X = Xwe,

e∈T

where the sum is over all the edges in T, and we is the weight of edge e. Define a “minimum-maximum spanning tree” to be a spanning tree that minimizes the quantity Y = maxwe. e∈T

That is, a minimum-maximum spanning tree has the smallest maximum edge weight out of all possible spanning trees.

(a) Prove that a minimum spanning tree in a connected weighted undirected graph G is always a minimum-maximum spanning tree for G.

[HINT: Suppose toward a contradiction that T is an MST but not a minimum-maximum spanning tree, and say that T0 is a minimum-maximum spanning tree. Let (u,v) be the heaviest edge in T. Then deleting (u,v) from T will disconnect it into two trees, A and B. Now use A and B and T0 to come up with a cheaper MST than T (and hence a contradiction).]

                                       
(b) Show that the converse to part (a) is not true. That is, a minimum-maximum spanning tree is not necessarily a minimum spanning tree.

 
(c) (Give a deterministic O(m) algorithm to find a minimum-maximum spanning tree in a connected weighted undirected graph G with n vertices and m edges.