This file contains the exercises,hints,and solutions for Chapter 9of the book ”Introduction to the Design and Analysis of Algorithms,”2nd edition,by
A.Levitin.The problems that might be challenging for at least some students are marked by  ;those that might be difficult for a majority of students are marked by  .
Exercises 9.1
1.Give an instance of the change-making problem for which the greedy al-gorithm does not yield an optimal solution.
2.Write a pseudocode of the greedy algorithm for the change-making prob-lem,with an amount n and coin denominations d 1>d 2>...>d m as its input.What is the time efficiency class of your algorithm?
3.Consider the problem of scheduling n jobs of known durations t 1,...,t n for execution by a single processor.The jobs can be executed in any order,one job at a time.You want to find a schedule that minimizes the total time spent by all the jobs in the system.(The time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution.)Design a greedy algorithm for this problem. Does the greedy algo-rithm always yield an optimal solution?
4.Design a greedy algorithm for the assignment problem (see Section 3.4).Does your greedy algorithm always yield an optimal solution?
5.Bridge crossing revisited Consider the generalization of the bridge cross-ing puzzle (Problem 2in Exercises 1.2)in which we have n >1people whose bridge crossing times are t 1,t 2,...,t n .All the other conditions of the problem remain the same:at most two people at the time can cross the bridge (and they move with the speed of the slower of the two)and they must carry with them the only flashlight the group has.
Design a greedy algorithm for this problem and find how long it will
take to cross the bridge by using this algorithm.Does your algorithm yields a minimum crossing time for every instance of the problem?If it does–prove it,if it does not–find an instance with the smallest number of people for which this happens.
6.Bachet-Fibonacci weighing problem Find an optimal set of n weights {w 1,w 2,...,w n }so that it would be possible to weigh on a balance scale any integer load in the largest possible range from 1to W ,provided a. weights can be put only on the free cup of the scale.
b. weights can be put on both cups of the scale.
1课后答案网 w w w .k h d a w .c o m
7.a.Apply Prim’s algorithm to the following graph.Include in the priority queue all the vertices not already in the tree.
b.Apply Prim’s algorithm to the following graph.Include in the priority queue only the fringe vertices (the vertices not in the current tree which are adjacent to at least one tree vertex).
8.The notion of a minimum spanning tree is applicable to a connected weighted graph.Do we have to check a graph’s connectivity before ap-plying Prim’s algorithm or can the algorithm do it by itself?9.a.How can we use Prim’s algorithm to find a spanning tree of a connected graph with no weights on its edges?
b.Is it a good algorithm for this problem?
10. Prove that any weighted connected graph with distinct weights has
exactly one minimum spanning tree.
11.Outline an efficient algorithm for changing an element’s value in a min-
heap.What is the time efficiency of your algorithm?2课后答案网 w h d a w .c o m
Hints to Exercises 9.1
1.As coin denominations for your counterexample,you may use,among a multitude of other possibilities,the ones mentioned in the text:d 1=7,d 2=5,d 3=1.
2.You may use integer divisions in your algorithm.
3.Considering the case of two jobs might help.Of course,after forming a hypothesis,you will have to either prove the algorithm’s optimality for an arbitrary input or find a specific counterexample showing that it is not the case.
4.You can apply the greedy approach either to the entire cost matrix or to each of its rows (or columns).
5.Simply apply the greedy approach to the situation at hand.You may assume that t 1≤t 2≤...≤t n .
6.For both versions of the problem,it is not difficult to get to a hypothesis about the solution’s form after considering the cases of n =1,2,and 3.It is proving the solutions’optimality that is at the heart of this problem.
7.a.Trace the algorithm for the graph given.An example can be found in the text of the section.
b.After the next fringe vertex is added to the tree,add all the unseen vertices adjacent to it to the priority queue of fringe vertices.
8.Applying Prim’s algorithm to a weighted graph that is not connected should help in answering this question.
9.a.Since Prim’s algorithm needs weights on a graph’s edges,some weights have to be assigned.
b.Do you know other algorithms that can solve this problem?10.Strictly speaking,the wording of the question asks you to prove two things:the fact that at least one minimum spanning tree exists for any weighted connected graph and the fact that a minimum spanning tree is unique if all the weights are distinct numbers.The proof of the former stems from the obvious observation about finiteness of the number of spanning trees for a weighted connected graph.The proof of the latter can be obtained by repeating the correctness proof of Prim’s algorithm with a minor adjustment at the end.
11.Consider two cases:the key’s value was decreased (this is the case needed for Prim’s algorithm)and the key’s value was increased.3课后答案网 w w w .k h d a w .c o m
Solutions to Exercises 9.1
1.Here is one of many such instances:For the coin denominations d 1=7,d 2=5,d 3=1and the amount n =10,the greedy algorithm yields one coin of denomination 7and three coins of denomination 1.The actual optimal solution is two coins of denomination 5.
2.Algorithm Change (n,D [1..m ])
/
/Implements the greedy algorithm for the change-making problem //Input:A nonnegative integer amount n and
//a decreasing array of coin denominations D
//Output:Array C [1..m ]of the number of coins of each denomination //in the change or the ”no solution”message
for i ←1to m do
C [i ]← n/
D [i ]
n ←n mod D [i ]
if n =0return C
else return ”no solution”
The algorithm’s time efficiency is in Θ(m ).(We assume that integer di-visions take a constant time no
matter how big dividends are.)Note also that if we stop the algorithm as soon as the remaining amount becomes 0,the time efficiency will be in O (m ).
3.a.Sort the jobs in nondecreasing order of their execution times and exe-cute them in that order.b.Yes,this greedy algorithm always yields an optimal solution.Indeed,for any ordering (i.e.,permutation)of the jobs i 1,i 2,...,i n ,the total time in the system is given by the formula t i 1+(t i 1+t i 2)+...+(t i 1+t i 2+...+t i n )=nt i 1+(n −1)t i 2+...+t i n .Thus,we have a sum of numbers n,n −1,...,1multiplied by “weights”t 1,
t 2,...t n assigned to the numbers in some order.To minimize such a sum,we have to assign smaller t ’s to larger numbers.In other words,the jobs should be executed in nondecreasing order of their execution times.Here is a more formal proof of this fact.We will show that if jobs are ex-ecuted in some order i 1,i 2,...,i n ,in which t i k >t i k +1for some k,then the total time in the system for such an ordering can be decreased.(Hence,no such ordering can be an optimal solution.)Let us consider the other job ordering,which is obtained by swapping the jobs k and k +1.Obvi-ously,the time in the systems will remain the same for all but these two 4课后答案网 w w w .k h d a w .c o m
sort of orderjobs.Therefore,the difference between the total time in the system for the new ordering and the one before the swap will be
[(k −1
j =1t i j +t i k +1)+(k −1
j =1t i j +t i k +1+t i k )]−[(k −1
j =1t i j +t i k )+(k −1
j =1t i j +t i k +t i k +1)]
=t i k +1−t i k <0.
4.a.The all-matrix version:Repeat the following operation n times.Select the smallest element in the unmarked rows and columns of the cost matrix and then mark its row and column.The row-by-row version:Starting with the first row and ending with the last row of the cost matrix,select the smallest element in that row which is not in a previously marked column.After such an element is selected,mark its column to prevent selecting another element from the same col-umn.b.Neither of the versions always yields an optimal solution.Here is
a simple counterexample:C = 122100 5.Repeat the following step n −2times:Send to the other side the
pair of two fastest remaining persons and then return the flashlight with the fastest person.Finally,send the remaining two people together.Assuming that t 1≤t 2≤...≤t n ,the total crossing time will be equal to (t 2+t 1)+(t 3+t 1)+...+(t n −1+t 1)+t n =n
i =2t i +(n −2)t 1=n  i =1t i +(n −3)t 1.Note:For an algorithm that always yields a minimal crossing time,see
Günter Rote,“Crossing the Bridge at Night,”EATCS Bulletin,vol.78(October 2002),241—246.
The solution to the instance of Problem 2in Exercises 1.2shows that the greedy algorithm doesn’t always yield the minimal crossing time for n >3.No smaller counterexample can be given as a simple exhaustive check for n =3demonstrates.(The obvious solution for n =2is the one generated by the greedy algorithm as well.)
5课后答案网 w w w .k
h d a w .c o m
6.a.Let’s apply the greedy approach to the first few instances of the problem in question.For n =1,we have to use w 1=1to balance weight 1.For n =2,we simply add w 2=2to balance the first previously una
ttainable weight of 2.The weights {1,2}can balance every integral weights up to their sum 3.For n =3,in the spirit of greedy thinking,we take the next previously unattainable weight:w 3=4.The three weights {1,2,4}allow to weigh any integral load l between 1and their sum 7,with l ’s binary expansion indicating the weights needed for load l :
Generalizing these observations,we should hypothesize that for any posi-tive integer n the set of consecutive powers of 2{w i =2i −1,i =1,2,...n }makes it possible to balance every integral load in the largest possible range,which is up to and including  n i =12i −1=2n −1.The fact that every integral weight l in the range 1≤l ≤2n −1can be balanced with this set of weights follows immediately from the binary expansion of l,which yields the weights needed for weighing l.(Note that we can obtain the weights needed for a given load l by applying to it the greedy algorithm for the change-making problem with denominations d i =2i −1,i =1,2,...n.)
In order to prove that no set of n weights can cover a larger range of consecutive integral loads,it will suffice to note that there are just 2n −1nonempty selections of n weights and,hence,no more than 2n −
1sums they yield.Therefore,the largest range of consecutive integral loads they can cover cannot exceed 2n −1.[Alternatively,to prove that no set of n weights can cover a larger range of consecutive integral loads,we can prove by induction on i that if any mul-tiset of n weights {w i ,i =1,...,n }–which we can assume without loss of generality to be sorted in nondecreasing order–can balance every integral load starting with 1,then w i ≤2i −1for i =1,2,...,n.The basis checks out immediately:w 1must be 1,which is equal to 21−1.For the general case,assume that w k ≤2k −1for every 1≤k <i.The largest weight the first i −1weights can balance is  i −1k =1w k ≤ i −1k =12
k −1=2i −1−1.If w i were larger than 2i ,then this load could have been balanced neither with the first i −1weights (which are too light even taken together)nor with the weights w i ≤...≤w n (which are heavier than 2i even individ-ually).Hence,w i ≤2i −1,which completes the proof by induction.This immediately implies that no n weights can balance every integral load up to the upper limit larger than  n i =1w i ≤ n i =12
i −1=2n −1,the limit attainable with the consecutive powers of 2weights.]
b.If weights can be put on both cups of the scale,then a larger range can 6课后答案网 w w w .k h d a w .

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。