This file contains the exercises, hints, and solutions for Chapter 9 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 9.1
1. Write pseudocode of the greedy algorithm for the change-making problem,
with an amount and coin denominations 1
2···
as its input.
What is the time efficiency class of your algorithm?
2. Design a greedy algorithm for the assignment problem (see Section 3.4).
Does your greedy algorithm always yield an optimal solution?
4. Compatible intervals Given open intervals (1
1)(2
2) (
)on the real line, each representing start and end times of some activity
requiring the same resource, the task is to find the largest number of these
intervals so that no two of them overlap. Investigate the three greedy
5. Bridge crossing revisited Consider the generalization of the bridge cross-
ing puzzle (Problem 2 in Exercises 1.2) in which we have 1people
whosebridgecrossingtimesare1
2 All the other conditions of
the problem remain the same: at most two people at the time can cross
1
6. BAveraging down There are 1identical vessels, one of them with
pints of water and the others empty. You are allowed to perform the
7. Rumor spreading There are people, each in possession of a different
rumor. They want to share all the rumors with each other by sending
8. Bachet’s problem of weights Find an optimal set of weights {1
2 }
so that it would be possible to weigh on a balance scale any integer load
in the largest possible range from 1 to ,provided
9. a. Apply Prim’s algorithm to the following graph. Include in the priority
queue all the vertices not already in the tree.
a b
5
2
are adjacent to at least one tree vertex).
ba
3
6
5
43
10. 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?
11. Does Prim’s algorithm always work correctly on graphs with negative edge
weights?
12. Let be a minimum spanning tree of graph obtained by Prim’s algo-
rithm. Let be a graph obtained by adding to a new vertex and
some edges, with weights, connecting the new vertex to some vertices in
Hints to Exercises 9.1
1. 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
6. Think the minimum positive amount of water among all the vessels in
their current state.
10. Applying Prim’s algorithm to a weighted graph that is not connected
should help in answering this question.
11. Check whether the proof of the algorithm’s correctness is valid for negative
edge weights.
14. 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
15. Consider two cases: the key’s value was decreased (this is the case needed
5
Solutions to Exercises 9.1
1. Algorithm Change( [1])
//Implements the greedy algorithm for the change-making problem
//Input: A nonnegative integer amount and
// a decreasing array of coin denominations
2. a. 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
3. a. Sort the intervals in nondecreasing order of their execution time and
execute them in that order.
6
Thus, we have a sum of numbers −1…,1 multiplied by “weights” 1
2…assigned to the numbers in some order. To minimize such a sum,
we have to assign smaller ’s to larger numbers. In other words, the jobs
should be executed in nondecreasing order of their execution time.
4. a. The greedy algorithm based on earliest start first doesn’t always yield
an optimal solution as the following counterexample shows: (0, 5), (1,
2), (3, 4). Selecting (0, 5) first makes selection of the other two intervals
impossible, whereas the optimal solution comprises both of them.
c. The greedy algorithm based on earliest finish first does always yield
an optimal solution. Let 1=(1
1) =(
)be intervals
7
5. Repeat the following step −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
1≤2≤ ≤the total crossing time will be equal to
6. Averaging the amount of water in the nonempty vessel successively with
each of the −1empty vessels, leaves 2−1pints in it. This is the
minimum amount of water achievable for that vessel. Indeed, consider
the minimum positive amount of water among all the vessels in their
7. There are several ways to accomplish the task by sending 2−2messages,
which is the minimum. In particular, this can be done by the following
8. a. Let’s apply the greedy approach to the first few instances of the problem
in question. For =1we have to use 1=1to balance weight 1For
=2we simply add 2=2to balance the first previously unattainable
weight of 2The weights {12}can balance every integral weights up to
their sum 3. For =3in the spirit of greedy thinking, we take the next
previously unattainable weight: 3=4The three weights {124}allow
to weigh any integral load between 1 and their sum 7, with ’s binary
expansion indicating the weights needed for load :
In order to prove that no set of weights can cover a larger range of
consecutive integral loads, it will suffice to note that there are just 2−1
nonempty selections of weights and, hence, no more than 2−1sums
they yield. Therefore, the largest range of consecutive integral loads they
can cover cannot exceed 2−1
9
b. If weights can be put on both cups of the scale, then a larger range can
be reached with weights for 1(For =1the single weight still
needs to be 1, of course.) The weights {13}enable weighing of every
integral load up to 4; the weights {139}enable weighing of every inte-
In fact, every positive integer can be uniquely represented in this form,
obtained from its ternary expansion as described above. For example,
5=12
3=1·31+2·30=1·31+(3−1) ·30=2·31−1·30
=(3−1) ·31−1·30=1·32−1·31−1·30
(Note that if we start with the rightmost 2, after a simplification, the new
rightmost 2, if any, will be at some position to the left of the starting one.
This proves that after a finite number of such replacements, we will be
able to eliminate all the 2’s.) Using the representation =P
10
9. a. Applying Prim’s algorithm to the graph
a b
5
we obtain
Tree vertices Priority queue of remaining vertices
a(-,-) b(a,5) c(a,7) d(a,∞)e(a,2)
11
b. Applying Prim’s algorithm to the graph given, we obtain
e f
d
c
ba
3
6
5
212
43
Tree vertices Priority queue of fringe vertices
a(-,-) b(a,3) c(a,5) d(a,4)
b(a,3) c(a,5) d(a,4) e(b,3) f(b,6)
e(b,3) c(a,5) d(e,1) f(e,2) i(e,4)
The minimum spanning tree found by the algorithm comprises the edges
10. There is no need to check the graph’s connectivity because Prim’s algo-
11. Prim’s algorithm does work correctly on graphs with negative edge weights.
One can deduce this from the fact that the proof of the algorithm’s cor-
12. The answer is no. In fact, the minimum spanning tree of the new graph can
comprise only edges connecting the new vertex to old ones. For example,
13. a. The simplest and most logical solution is to assign all the edge weights
to 1.
14. The number of spanning trees for any weighted connected graph is a pos-
itive finite number. (At least one spanning tree exists, e.g., the one
obtained by a depth-first search traversal of the graph. And the number
of spanning trees must be finite because any such tree comprises a subset
of edges of the finite set of edges of the given graph.) Hence, one can
15. If a key’s value in a min-heap was decreased, it may need to be pushed
up (via swaps) along the chain of its ancestors until it is smaller than or
equal to its parent or reaches the root. If a key’s value in a min-heap was
13
Exercises 9.2
1. Apply Kruskal’s algorithm to find a minimum spanning tree of the follow-
ing graphs.
a.
b.
ba
3
6
5
43
2. Indicate whether the following statements are true or false:
a. If is a minimum-weight edge in a connected weighted graph, it must
be among edges of at least one minimum spanning tree of the graph.
3. What changes, if any, need to be made in algorithm Kruskal to make it
find a minimum spanning forest for an arbitrary graph? (A minimum
6. Rewrite pseudocode of Kruskal’s algorithm in terms of the operations of
the disjoint subsets’ ADT.
10. Design and conduct an experiment to empirically compare the efficiencies
of Prim’s and Kruskal’s algorithms on random graphs of different sizes
and densities.
16
Hints to Exercises 9.2
1. Trace the algorithm for the given graphs the same way it is done for
another input in the section.
5. Is the general trick of transforming maximization problems to their mini-
mization counterparts (see Section 6.6) applicable here?
6. Substitute the three operations of the disjoint subsets’ ADT–makeset(),
find()and union( )–in the appropriate places of the algorithm’s
pseudocode given in the section.
11. The question is not trivial, because introducing extra points (called Steiner
points ) may make the total length of the network smaller than that of a
17
Solutions to Exercises 9.2
1. a.
Tree Sorted list of edges Illustration
edges (selected edges are shown in bold)
bc
1de
2bd
3cd
4ab
5ad
6ce
6
a
b
d
1c
e
5
62
6
34
b
1c
18
b.
ba
3
6
5
43
ba
3
6
5
43
⇒
ba
3
6
5
43
ba
3
6
5
43
⇒
ba
3
6
5
43
ba
3
6
5
43
19
ba
3
6
5
43
ba
3
6
5
43
⇒
ba
3
6
5
43
ba
3
6
5
43
⇒
ba
3
6
5
43
ba
3
6
5
43
2. a. True. (Otherwise, Kruskal’s algorithm would be invalid.)
b. False. As a simple counterexample, consider a complete graph with