This file contains the exercises, hints, and solutions for Chapter 3 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 3.1
1. a. Give an example of an algorithm that should not be considered an
2. a. What is the efficiency of the brute-force algorithm for computing
as a function of ? As a function of the number of bits in the binary
representation of ?
3. For each of the algorithms in Problems 4, 5, and 6 of Exercises 2.3, tell
whether or not the algorithm is based on the brute-force approach.
4. a. Design a brute-force algorithm for computing the value of a polynomial
5. A network topology specifies how computers, printers, and other devices
are connected over a network. The figure below illustrates three common
topologies of networks: Ring, Star, and Fully Connected Mesh.
1
6. Tetromino tilings Tetrominoes are tiles made of four 1×1 squares There
are five types of tetrominoes shown below:
7. A stack of fake coins There are stacks of identical-looking coins. All
of the coins in one of these stacks are counterfeit, while all the coins in
the other stacks are genuine. Every genuine coin weighs 10 grams; every
fake weighs 11 grams. You have an analytical scale that can determine
the exact weight of any number of coins.
8. Sort the list in alphabetical order by selection sort.
9. Is selection sort stable? (The definition of a stable sorting algorithm was
given in Section 1.3.)
2
c. Prove that the worst-case efficiency of the improved version is quadratic.
13. Is bubble sort stable?
14. Alternating disks You have a row of 2disks of two colors, dark and
light. They alternate: dark, light, dark, light, and so on. You want to
get all the dark disks to the right-hand end, and all the light disks to the
Hints to Exercises 3.1
1. a. Think of algorithms that have impressed you with their efficiency
and/or sophistication. Neither characteristic is indicative of a brute-
2. a. The first question was all but answered in the section. Expressing
the answer as a function of the number of bits can be done by using the
formularelatingthetwometrics.
b. How can we compute ()mod?
5. For each of the three network topologies, what properties of the matrix
should the algorithm check ?
6. The answer to four of the questions is “yes”.
7. a. Just apply the brute-force thinking to the problem in question.
b. The problem can be solved in one weighing.
4
12. a. A list is sorted if and only if all its adjacent elements are in a correct
order. Why?
5
Solutions to Exercises 3.1
1. a. Euclid’s algorithm and the standard algorithm for finding the binary
representation of an integer are examples from the algorithms previously
2. a. ()=≈2where ()is the number of multiplications made by
the brute-force algorithm in computing and is the number of bits in
3. Problem 4 (computes P
12):yes
4. a. Here is a pseudocode of the most straightforward version:
Algorithm BruteForcePolynomialEvaluation([0])
//The algorithm computes the value of polynomial at a given point
6
b. The above algorithm is very inefficient: we recompute powers of again
and again as if there were no relationship among them. Thus, the obvious
improvement is based on computing consecutive powers more efficiently.
If we proceed from the highest term to the lowest, we could compute
Algorithm BetterBruteForcePolynomialEvaluation([0])
//The algorithm computes the value of polynomial at a given point
The number of multiplications here is
()=
X
=1
2=2
7
5. For simplicity, we check each of the three topologies separately.
The adjacency matrix of a graph with the ring topology must be, of course,
symmetric, and each of its rows must have exactly two 1’s, both not on the
The following brute-force algorithm follows the 1’s in a given matrix indicating
twoedgesincidentwithavertex: onefortheedgeenteringitandtheother
leaving the vertex, making sure the cycle closes at the starting vertex only after
visiting all the other vertices of the graph.
Start by scanning row 0 to verify that it has exactly two 1’s in columns we
denote 1and −1so that 0
1
−1. If it is not the case, stop: the matrix
is not the adjacency matrix of a graph with the ring topology. If it is the case,
Thetimeefficiency of the algorithm is (2)because it checks all the ele-
ments of an ×matrix in the worst case.
Note: It is not difficult to prove that a graph has the ring topology if and only
if all its vertices have degree 2 while having no loops, and it is connected. Hence
8
to check whether it contains all 1’s except in column 0 or it contains a single 1
in some column 00In the former case, every subsequent row =12
−1must contain a single 1 in column 0 (i.e., [ 0] = 1 and [ ]=0for
6. Tilings of an 8×8board with straight tetrominoes, square tetrominoes, L-
tetrominoes, and T-tetrominoes are shown below. It is impossible to cover
9
in the first row.
(a) (b)
(c) (d)
10
7. a. Number the coin stacks from 1 to Starting with the first stack, repeat
the following. If the current stack is not the last one, take any coin from
the stack and weigh it: if it weighs 11 grams, this stack contains the fake
coins and algorithm stops; if the coin weighs 10 grams, proceed to the next
8. A
E
9. Selection sort is not stable: In the process of exchanging elements that are
not adjacent to each other, the algorithm can reverse an ordering of equal
elements. The list 20,2
00, 1 is such an example.
11
11. , ,,
?
↔?
↔
?
↔
?
↔
?
↔
?
↔
|
12. a. Pass (0 ≤≤−2) of bubble sort can be represented by the following
diagram:
0
?
↔+1 −−1≤|−≤···≤−1
in their final positions
If there are no swaps during this pass, then
b. Here is a pseudocode for the improved version of bubble sort:
Algorithm BetterBubbleSort([0 −1])
12
13. Bubble sort is stable. It follows from the fact that it swaps adjacent
elements only, provided [+1][]
14. Here is a simple and efficient (in fact, optimal) algorithm for this problem:
Starting with the first and ending with the last light disk, swap it with
13
Exercises 3.2
1. Find the number of comparisons made by the sentinel version of sequential
search
2. As shown in Section 2.1, the average number of key comparisons made by
sequential search (without a sentinel, under standard assumptions about
3. Gadget testing Afirm wants to determine the highest floor of its -story
headquarters from which a gadget can fall without breaking. The firm has
4. Determine the number of character comparisons made by the brute-force
algorithm in searching for the pattern GANDHI in the text
5. How many comparisons (both successful and unsuccessful) are made by the
brute-force string-matching algorithm in searching for each of the following
patterns in the binary text of 1000 zeros?
a. 00001 b. 10000 c. 01010
14
8. Consider the problem of counting, in a given text, the number of substrings
that start with an A and end with a B. (For example, there are four such
9. Write a visualization program for the brute-force string-matching algo-
rithm.
10. Word Find A popular diversion in the United States, “word find” (or
“word search”) puzzles ask the player to find each of a given set of words
in a square table filled with single letters. A word can read horizontally
11. Battleship game Write a program for playing Battleship (a classic strat-
egy game) on the computer which is based on a version of brute-force
pattern matching. The rules of the game are as follows. There are two
opponents in the game (in this case, a human player and the computer).
Hints to Exercises 3.2
2. As a function of , what kind of function is ?
5. For each input, one iteration of the algorithm yields all the information
you need to answer the question.
6. It will suffice to limit your search for an example to binary texts and
patterns.
9. You may use either bit strings or a natural language text for the visual-
ization program. It would be a good idea to implement, as an option, a
search for all occurrences of a given pattern in a given text.
11. A (very) brute-force algorithm can simply shoot at adjacent feasible cells
starting at, say, one of the corners of the board. Can you suggest a better
Solutions to Exercises 3.2
1. a. ()=+1
2+(+1)(1−)=(2 −)(+1)
2
2. The expression
(+1)
2+(1 −)=+1
2+− =−(−+1
2)=−−1
2
3. Drop the first gadget from floors d√e2d√eandsoonuntileitherthe
floor d√ea drop from which makes the gadget malfunction is reached
or no such floor in this sequence is encountered before the top of the
building is reached. In the former case, the floor to be found is higher
4. 43 comparisons.
The algorithm will make 47 −6+1 = 42 trials: In the first one, the G
of the pattern will be aligned against the first T of the text; in the last
5. a. For the pattern 00001, the algorithm will make four successful and one
unsuccessful comparison on each of its trials and then shift the pattern
one position to the right:
000000 00000
00001
c. For the pattern 01010, the algorithm will make one successful and
one unsuccessful comparison on each of its trials and then shift the pat-
tern one position to the right:
000000 00000
6. The text composed of zeros and the pattern 0 0
|{z }
−1
1isanexampleof
the worst-case input. The algorithm will make (−+1) character
comparisons on such input.
7. Comparing pairs of the pattern and text characters righ-to-left can allow
farther pattern shifts after a mismatch. This is the main insight the two
8. a. Note that the number of desired substrings that starts with an A at a
given position (0 ≤−1) in the text is equal to the number of B’s
to the right of that position. This leads to the following simple algorithm:
b. Note that the number of desired substrings that ends with a B at
agivenposition(0 ≤−1) in the text is equal to the number of A’s
to the left of that position. This leads to the following algorithm:
9. n/a
19
Exercises 3.3
1. Assuming that sqrt takes about ten times longer than each of the other
2. Can you design a more efficient algorithm than the one based on the brute-
forcestrategytosolvetheclosest–pairproblemforpoints 1 on
the real line?
3. Let 1
2 be real numbers representing coordinates of
4. a.BThere are several alternative ways to define a distance between two
points 1(1
1)and 2(2
2). In particular, the Manhattan distance
is defined as
(1
2)=|1−2|+|1−2|
b. Sketch all the points in the coordinate plane whose Manhattan
distance to the origin (0,0) is equal to 1. Do the same for the Euclidean
distance.
20