Chapter 11 Prove that any comparison-based algorithm for

This ﬁle contains the exercises, hints, and solutions for Chapter 11 of the

book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by

Exercises 11.1

1. Prove that any algorithm solving the alternating-disk puzzle (Problem 14

inExercises3.1)mustmakeatleast(+1)2moves to solve it. Is this

lower bound tight?

2. Prove that the classic recursive algorithm for the Tower of Hanoi problem

3. Find a trivial lower-bound class for each of the following problems and

indicate, if you can, whether this bound is tight.

4. Consider the problem of identifying a lighter fake coin among identical-

looking coins with the help of a balance scale. Can we use the same

information-theoretic argument as the one in the text for the number of

questions in the guessing game to conclude that any algorithm for identi-

fying the fake will need at least dlog2eweighings in the worst case?

5. Prove that any comparison-based algorithm for ﬁnding the largest element

of an -element set of numbers must make −1comparisons in the worst

case.

9. Find the product of matrices and through a transformation to a

product of two symmetric matrices if

b. Show that multiplication of two matrices of order can be reduced

to squaring a matrix of order 2

11. Find a tight lower bound class for the problem of ﬁnding two closest

2

Hints to Exercises 11.1

1. Is it possible to solve the puzzle by making fewer moves than the brute-

force algorithm? Why?

2. Since you know that the number of disk moves made by the classic algo-

rithm is 2−1you can simply prove (e.g., by mathematical induction)

3. All these questions have straightforward answers. If a trivial lower bound

4. Reviewing Section 4.4, where the fake-coin problem was introduced, should

help in answering the question.

5. Pay attention to comparison losers.

9. Simply follow the transformation formula suggested in the section.

10. a. Check whether the formulas hold for two arbitrary square matrices.

b. Use a formula similar to the one showing that multiplication of ar-

bitrary square matrices can be reduced to multiplication of symmetric

matrices.

Solutions to Exercises 11.1

1. In the initial position of the puzzle, the th light disk has exactly dark

disks to the left of it (=12  )Hence the total number of the dark

2. Let ()be the number of disk moves made by some algorithm solving

the Tower of Hanoi problem. We’ll prove by induction that

()≥2−1for ≥1

For the basis case of =1(1) ≥21−1holds. Assume now that the

3. a. All elements of a given array need to be processed to ﬁnd its largest

element (otherwise, if an unprocessed element is larger than all the others,

the output cannot be correct) and just one item needs to be produced (if

just the value of the largest element or a position of the largest element

needs to be returned). Hence the trivial lower bound is linearIt is tight

4. The answer is no. The problem can be solved with fewer weighings by

dividing the coins into three rather than two subsets with about the same

5. Every comparison of two (distinct) elements produces one “winner” and

6. Recall that an inversion in an array is any pair of its elements that are

out of order, i.e., [][]while  The maximum number of

inversions in an -element array is attained when its elements are strictly

7. Consider the following rule for the adversary to follow: Divide the set

of vertices of an input graph into two disjoints subsets and hav-

ing b2cand d2evertices respectively (e.g., by putting the ﬁrst b2c

vertices into and the remaining d2evertices into )Whenever an

algorithm inquires about an edge between two vertices, reply yes if and

8. Any comparison-based algorithm will need at least 2comparisons to

merge two arbitrary sorted lists of sizes and +1, respectively. The

9. For =∙1−1

23

¸and =∙01

−12

¸the respective transposes are

=∙12

−13

¸and =∙0−1

12

¸

10. a. The formula  =1

4[(+)2−(−)2]does not hold for arbitrary

square matrices because it relies on commutativity of multiplication (i.e.,

 =):

11. The element uniqueness problem can be reduced to the closest numbers

problem. (After solving the latter, it suﬃces to check whether the distance

12. Sorting a list of numbers is a special case of the number placement prob-

lem. This implies that Ω(log )the lower bound for sorting, is also a

Exercises 11.2

1. Prove by mathematical induction that

2. Consider the problem of ﬁnding the median of a three-element set { 

}of orderable items

a. What is the information-theoretic lower bound for comparison-based

algorithms solving this problem?

3. Draw a decision tree and ﬁnd the number of key comparisons in the worst

and average cases for

4. Design a comparison-based algorithm for sorting a four-element array with

the smallest number of element comparisons possible.

7. BCompare the two lower bounds for searching a sorted array–dlog3(2+

1)eand dlog2(+1)e–to show that

9. A tournament tree is a complete binary tree reﬂecting results of a

“knockout tournament”: its leaves represent players entering the tour-

nament, and each internal node represents a winner of a match played by

the players represented by the node’s children. Hence, the winner of the

tournament is represented by the root of the tree.

a. What is the total number of games played in such a tournament?

10. Advanced fake-coin problem There are ≥3coins identical in appear-

ance; either all are genuine or exactly one of them is fake. It is unknown

whether the fake coin is lighter or heavier than the genuine one. You have

a balance scale with which you can compare any two sets of coins. That

a. Prove that any algorithm for this problem must make at least dlog3(2+

1)eweighings in the worst case.

b. Draw a decision tree for an algorithm that solves the problem for

=3coins in two weighings.

11. Jigsaw puzzle A jigsaw puzzle contains pieces. A “section” of the

puzzle is a set of one or more pieces that have been connected to each

other. A “move” consists of connecting two sections. What algorithm

will minimize the number of moves required to complete the puzzle?

Hints to Exercises 11.2

1. a. Prove ﬁrst that 2≥by induction on 

b. Prove ﬁrst that 3≥by induction on 

3. This is a straightforward question. You may assume that three elements

to be sorted are distinct. (If you need help, see decision trees for the three-

element selection sort and three-element insertion sort in the section).

4. Compute a nontrivial lower bound for sorting a four-element array and

7. a. Start by transforming the logarithms to the same base.

b. The easiest way is to prove that

8. The answer to the ﬁrst question follows directly from inequality (11.1).

The answer to the second is no (why?).

9. a. Think losers.

10. a. How many outcomes does this problem have?

b. Draw a ternary decision tree that solves the problem.

11. If you want to solve the problem in the spirit of the section, represent a

process of assembling the puzzle by a binary tree.

Solutions to Exercises 11.2

1. a. We’ll prove by induction on that that 2≥for any nonempty binary

tree with height ≥0and the number of leaves  For the basis case of

=0we have 20≥1For the general case, assume that 2≥holds

for any binary tree whose height doesn’t exceed  Consider an arbitrary

2. a. Since the problem has three possible outcomes, the information-theoretic

lower bound is dlog23e=2

b. Here is a decision tree for an algorithm for the problem of ﬁnding

the median of a three-element set {  }:

a < b

yes no

12

comparison (unless it’s the same as the ﬁrst one) will compare the third

number with one of these endpoints. If that third number is compared to

the left end of the interval and it is larger than it, it would be impossible

3. a. Here is a decision tree for sorting an array of three distinct elements a,

b, and c by basic bubble sort:

a < b

yes no

abc

abc bac

b. Here is a decision tree for sorting an array of three distinct elements

by enhanced bubble sort:

a < b

yes no

abc

4. dlog24!e=5Mergesort (as described in Section 5.1) sorts any four-

5. The following solution is presented by Knuth [KnuIII, pp. 183—184]. Let

     be ﬁve distinct elements to be sorted. First, we compare with

and with  Without loss of generality we can assume that and

 This can be depicted by the following digraph of ﬁve vertices, in

which a path indicates an ordered subsequence:

following situations:

6. Here is a decision tree for searching a four-element ordered list (indexed

from0to3)bysequentialsearch:

<>

A[0]

7. a. Since ≤implies de≤de(because ≤≤deand therefore, since

deis an integer, de≤deby the deﬁnition of de)it will suﬃce to show

that

log3(2+1)≤log2(+1)for every ≥1

15

One way to prove that the last inequality holds for every ≥1is to

consider the function

b. The easiest way is to prove a stronger assertion:

lim

→∞

dlog2(+1)e

dlog3(2+1)e1

Indeed, using l’Hôpital’s Rule, we obtain the following:

lim

→∞

()−1

()+1 =lim

→∞

log2(+1)−1

log3(2+1)+1

=lim

→∞

1

+1 ·1

ln 2

1

2+1 ·2

ln 3

=ln 3

ln 2 =log

23

Computing the limit of ()+1

()−1in the exactly same way yields the same

result. Therefore, according to a well-known theorem of calculus,

16

8. Since any of the numbers can be the maximum, the number of leaves

in a decision tree of any algorithm solving the problem will be at least 

9. a. Before a winner can be determined, −1players must lose a game.

Since each game results in one loser, −1games are played in a single-

elimination tournament with players.

b. The tournament tree has leaves (the number of players) and −1in-

ternal nodes (the number of games–see part a). Hence the total number

of nodes in this binary tree is 2−1and, since it is complete, its height

10. a. Since each of the coins can be either lighter or heavier than all the

others and all the coins can be genuine, the total number of possible out-

comes is 2+1Since each weighing can have three results, the smallest

number of weighings must be at least dlog3(2+1)e

b. In the decision tree below, the coins are numbered from 1 to 3. Internal

1:2

<

>

1 – 2 + = 3 1+ 2 –

= +

–

+

–

=

+

–

123

+

–

c. There are two reasonable possibilities for the ﬁrst weighing: to weigh

two coins (i.e., one on each cup of the scale) and to weigh four coins (i.e.,

two on each cup). If an algorithm weighs two coins and they weigh the

d. Here is a decision three of an algorithm that solves the fake-coin puzzle

for =4in two weighings by using an extra coin (denoted )knownto

be genuine:

–

1, 2 : 3, g

<

>

= 1 2 3 4

+

– ++

–+

–

=

18

e. Here is a decision tree of an algorithm that solves the fake-coin puzzle

for 12 coins in three weighings

1,2,3,4 : 5,6,7,8

<>

=

–

+–

+

1 2–

+

3–

+

4–

+

5–

+–

+

7–

+

8–

+

9

6–

+–

+

11 –

+

12

10

=

Note: This problem is discussed on many puzzle-related sites on the In-

ternet (see, e.g., http://www.cut-the-knot.com/blue/weight1.shtml). The

attractiveness of the solution given above lies in its symmetry: the sec-

ond weighings involve the same coins if the ﬁrst one tips the scale either

11. Any algorithm to assemble the puzzle can be represented by a binary tree

whose leaves represents the single pieces and internal nodes represent con-

necting two sections (its children). Since each internal node in such a tree

has two children, the leaves can be interpreted as extended nodes of a tree

19