This file contains the exercises, hints, and solutions for Chapter 4 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3d edition, by
Exercises 4.1
1. Ferrying soldiers A detachment of soldiers must cross a wide and deep
river with no bridge in sight. They notice two 12-year-old boys playing
2. Alternating glasses a. There are 2glasses standing next to each other
in a row, the first of them filled with a soda drink while the remaining
3. Marking cells Design an algorithm for the following task. For any even
mark cellsonaninfinite sheet of graph paper so that each marked
4. Design a decrease-by-one algorithm for generating the power set of a set
of elements. (The power set of a set is the set of all the subsets of ,
including the empty set and itself.)
5. Consider the following algorithm to check connectivity of a graph defined
by its adjacency matrix.
1
6. Team ordering You have results of a completed round-robin tournament
in which teams played each other once. Each game ended either with a
victory of one the teams or with a tie. Design an algorithm that lists the
teams in a sequence so that every team did not loose the game with the
team listed immediately after it. What is the time efficeincy class of your
algorithm?
9. Is it possible to implement insertion sort for sorting linked lists? Will it
have the same (2)efficiency as the array version?
10. Consider the following version of insertion sort.
11. Let [0 −1] be an array of sortable elements. (For simplicity, you
can assume that all the elements are distinct.) Recall that a pair of its
elements ([][]) is called an inversion if and [][].
2
12. Shellsort (more accurately Shell’s sort) is an important sorting algorithm
which works by applying insertion sort to each of several interleaving sub-
lists of a given list. On each pass through the list, the sublists in question
Hints to Exercises 4.1
1. Solve the problem for =1
5. The answer is “no.”
6. Use the same idea that underlies insertion sort.
10. Since the only difference between the two versions of the algorithm is in the
inner loop’s operations, you should estimate the difference in the running
times of one repetition of this loop.
4
Solutions to Exercises 4.1
1. First, the two boys take the boat to the other side, after which one of
them returns with the boat. Then a soldier takes the boat to the other
2. a. Assuming that the glasses are numbered left to right from 1 to 2 pour
soda from glass 2 into glass 2−1This makes the first and last pair of
glasses alternate in the required pattern and hence reduces the problem to
thesameproblemwith2(−2) middle glasses. If is even, the number
of times this operation needs to be repeated is equal to 2; if is odd, it
3. For =2, an obvious solution is depicted in the figure below (the first
figure) . Marking two cells adjacent to, say, the rightmost cell in this
solution–one horizontally and the other vertically (say, up)–yields a so-
cell, yields a solution for =6(the right figure). In this manner, we can
solve the puzzle for any even value of .
4. Here is a general outline of a recursive algorithm that create list ()of
all the subsets of {1 }(see a more detailed discussion in Section 4.3):
5. Thelineifnot Connected ([0 −20 −2]) return 0 is incorrect. As
a counter-example, consider a graph in which the first −1points have no
edges between them but each has an edge connecting it to the th vertex.
6. Initialize the desired list with any of the teams. For each of the other
teams,scanthelisttoinsertitbeforethefirstteamitdidn’tlooseoratthe
7. Sorting the list ,,,,in alphabetical order with insertion
sort:
X
8. a. –∞or, more generally, any value less than or equal to every element in
the array.
9. Yes, but we will have to scan the sorted part left to right while inserting
[]to get the same (2)efficiency as the array version
10. The efficiency classes of both versions will be the same. The inner loop
of InsertionSort consists of one key assignment and one index decrement;
11. a. The largest number of inversions for [](0≤≤−1) is −1−;
this happens if []is greater than all the elements to the right of it.
Therefore, the largest number of inversions for an entire array happens for
a strictly decreasing array. This largest number is given by the sum:
b. Assuming that all elements are distinct and that inserting []in each
of the +1possible positions among its predecessors is equally likely, we
obtain the following for the expected number of key comparisons on the
th iteration of the algorithm’ssentinelversion:
7
of key comparisons on the th iteration of the no-sentinel version is:
1
+1
X
=1
+
+1 =1
+1
(+1)
2+
+1 =
2+
+1
Hence, for the average number of key comparisons, ()we have
The second sum can be estimated as follows:
12. a. Applying shellsort to the list 11122314223
with the step-sizes 13, 4, and 1 yields the following. (If a comparison causes
8
a swap, only the swap’s result is shown.)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
1
1122
3142
23
21
12
3
1
4
24
21
The final pass with the step-size 1–sorting the last array by insertion
sort–is omitted from the solution because of its simplicity. Note that
since relatively few elements in the last array are out of order as a result
of the work done on the preceding passes of shellsort, insertion sort will
need significantly fewer comparisons to finish the job than it would have
needed if it were applied to the initial array.
b. Shellsort is not stable. As a counterexample for shellsort with the
9
Exercises 4.2
1. Apply the DFS-based algorithm to solve the topological sorting problem
for the following digraphs:
(b)
.
2. a. Prove that the topological sorting problem has a solution for a digraph
if and only if it is a dag.
4. Can one use the order in which vertices are pushed onto the DFS stack
(instead of the order they are popped offit) to solve the topological sorting
problem?
5. Apply the source-removal algorithm to the digraphs of Problem 1.
6. a. Prove that a dag must have at least one source.
7. BCan you implement the source-removal algorithm for a digraph repre-
sented by its adjacency lists so that its running time is in (||+||)?
10
from to In general, a digraph’s vertices can be partitioned into dis-
joint maximal subsets of vertices that are mutually accessible via directed
paths of the digraph; these subsets are called strongly connected com-
ponents. There are two DFS-based algorithms for identifying strongly
connected components. Here is the simpler (but somewhat less efficient)
one of the two:
Step 1 Do a DFS traversal of the digraph given and number its vertices
in the order that they become dead ends.
a. Apply this algorithm to the following digraph to determine its strongly
connected components.
e
b
e
a
d
c
10. Spiders’s web A spider sits at the bottom (point S) of its web, while a fly
sits at the top (F). How many different ways can the spider reach the fly
by moving along the web’s lines in the directions indicated by the arrows?
[Kor05]
F
S
12
Hints to Exercises 4.2
1. Trace the algorithm as it is done in the text for another digraph (see Fig.
4.7).
4. Trytodothisforasmallexampleortwo.
5. Trace the algorithm on the instances given as it is done in the section (see
Fig. 4.8).
7. For each vertex, store the number of edges entering the vertex in the
remaining subgraph. Maintain a queue of the source vertices.
9. a. Trace the algorithm on the input given by following the steps of the
algorithm as indicated.
10. Take advantage of topological sorting and the graph’s symmetry.
Solutions to Exercises 4.2
1. a. The digraph and the stack of its DFS traversal that starts at vertex
are given below:
b. The digraph below is not a dag. Its DFS traversal that starts at
encounters a back edge from to :
b
a
c d
2. a. Let us prove by contradiction that if a digraph has a directed cycle,
then the topological sorting problem does not have a solution. Assume
that 1 is a solution to the topological sorting problem for a di-
graph with a directed cycle. Let be the leftmost vertex of this cycle
vertices solves the topological sorting problem. Hence, the answer to the
question is !
3. a. Since reversing the order in which vertices have been popped offthe
DFS traversal stack is in Θ(||)the running time of the algorithm will
be the same as that of DFS (except for the fact that it can stop before
4. The answer is no. Here is a simple counterexample:
b
a c
5. a.
d
g
a
c
f
b
e
delete d
g
a
c
f
b
e
delete a
6. a. Assume that, on the contrary, there exists a dag with every vertex
having an incoming edge. Reversing all its edges would yield a dag with
every vertex having an outgoing edge. Then, starting at an arbitrary ver-
7. The answer to this well-known problem is yes (see, e.g., [KnuI], pp. 264-
265).
8. n/a
16
The stack of the first DFS traversal, with as its starting vertex, will
look as follows:
1
The digraph with the reversed edges is
b
4
a43
8
c
ThestackandtheDFStrees(withonlytreeedgesshown)oftheDFS
traversal of the second digraph will be as follows:
c
d a
b. If a graph is represented by its adjacency matrix, then the efficiency
of the first DFS traversal will be in Θ(||2)The efficiency of the edge-
reversal step (set [ ]to 1 in the adjacency matrix of the new digraph
if [ ]=1in the adjacency matrix of the given digraph and to 0 other-
17
10. The total number of directed paths from S to a vertex of the spider’s
digraph can be obtained as the sum of the directed paths from S to all
the vertices for which there is a directed edge from to Because
of the digraph’s symmetry with respect to the “straight” four-edge path
C
D
I
I
J
K
O
18
Exercises 4.3
1. Is it realistic to implement an algorithm that requires generating all per-
mutations of a 25-element set on your computer? What about all the
subsets of such a set?
2. Generate all permutations of {1234}by
3. Write a program for generating permutations in lexicographic order.
4. IConsider a simple implementation of the following algorithm for gener-
ating permutations discovered by B. Heap [Hea63].
a. Trace the algorithm by hand for =23and 4
b. Prove the correctness of Heap’s algorithm.
c. What is the time efficiency of this algorithm?
5. Generate all the subsetsofafour–elementset={1
2
3
4}by each
of the two algorithms outlined in this section.
19
9. a. Generate the binary reflexiveGraycodeoforder4
b. Trace the following nonrecursive algorithm to generate the binary re-
10. IDesign a decrease-and-conquer algorithm for generating all combina-
tions of items chosen from i.e., all -element subsets of a given –
element setIs your algorithm a minimal-change algorithm?
11. Gray code and the Tower of Hanoi
(a) BShow that the disk moves made in the classic recursive algorithm
12. Fair attraction In olden days, one could encounter the following attrac-
tion at a fair. A light bulb was connected to several switches in such a
way that it lighted up only when all the switches were closed. Each switch