The control of a large force is the same principle as the control of a few men:
it is merely a question of dividing up their numbers.
— Sun Zi, The Art of War (c. �����), translated by Lionel Giles (����)Our life is frittered away by detail. . . . Simplify, simplify.
— Henry David Thoreau, Walden (�8��)
Now, don’t ask me what Voom is. I never will know.
But, boy! Let me tell you, it DOES clean up snow!
— Dr. Seuss [Theodor Seuss Geisel], The Cat in the Hat Comes Back (���8)
Do the hard jobs �rst. The easy jobs will take care of themselves.
— attributed to Dale Carnegie�
Recursion
�.�

Reductions

Reduction is the single most common technique used in designing algorithms.
Reducing one problem X to another problem Y means to write an algorithm
for X that uses an algorithm for Y as a black box or subroutine. Crucially, thecorrectness of the resulting algorithm for X cannot depend in any way on how
the algorithm for Y works. The only thing we can assume is that the black box
solves Y correctly. The inner workings of the black box are simply none of ourbusiness; they’re somebody else’s problem. It’s often best to literally think of theblack box as functioning purely by magic.
For example, the peasant multiplication algorithm described in the previous
chapter reduces the problem of multiplying two arbitrary positive integers to
three simpler problems: addition, mediation (halving), and parity-checking. The
algorithm relies on an abstract “positive integer” data type that supports those
three operations, but the correctness of the multiplication algorithm does not���. R��������

depend on the precise data representation (tally marks, clay tokens, Babylonian
hexagesimal, quipu, counting rods, Roman numerals, finger positions, augrym
stones, gobar numerals, binary, negabinary, Gray code, balanced ternary, phinary,quater-imaginary, . . . ), or on the precise implementations of those operations.
Of course, the running time of the multiplication algorithm depends on therunning time of the addition, mediation, and parity operations, but that’s
a separate issue from correctness. Most importantly, we can create a more
efficient multiplication algorithm just by switching to a more efficient number
representation (from tally marks to place-value notation, for example).
Similarly, the Huntington-Hill algorithm reduces the problem of apportioning
Congress to the problem of maintaining a priority queue that supports theoperations I
and E
M . The abstract data type “priority queue” isa black box; the correctness of the apportionment algorithm does not dependon any specific priority queue data structure. Of course, the running time of
the apportionment algorithm depends on the running time of the I
andE
M algorithms, but that’s a separate issue from the correctness of thealgorithm. The beauty of the reduction is that we can create a more efficient
apportionment algorithm by simply swapping in a new priority queue data
structure. Moreover, the designer of that data structure does not need to knowor care that it will be used to apportion Congress.
When we design algorithms, we may not know exactly how the basic building
blocks we use are implemented, or how our algorithms might be used as building
blocks to solve even bigger problems. That ignorance is uncomfortable for many
beginners, but it is both unavoidable and extremely useful. Even when you
do know precisely how your components work, it is often extremely helpful topretend that you don’t.

�.�

Simplify and Delegate

Recursion is a particularly powerful kind of reduction, which can be describedloosely as follows:• If the given instance of the problem can be solved directly, solve it directly.
• Otherwise, reduce it to one or more simpler instances of the same problem.
If the self-reference is confusing, it may be helpful to imagine that someone elseis going to solve the simpler problems, just as you would assume for other typesof reductions. I like to call that someone else the Recursion Fairy. Your only
task is to simplify the original problem, or to solve it directly when simplificationis either unnecessary or impossible; the Recursion Fairy will solve all the simpler
subproblems for you, using Methods That Are None Of Your Business So Butt���.�. Simplify and Delegate

Out. Mathematically sophisticated readers might recognize the Recursion Fairy
by its more formal name: the Induction Hypothesis.
There is one mild technical condition that must be satisfied in order for
any recursive method to work correctly: There must be no infinite sequence of
reductions to simpler and simpler instances. Eventually, the recursive reductions
must lead to an elementary base case that can be solved by some other method;otherwise, the recursive algorithm will loop forever. The most common way
to satisfy this condition is to reduce to one or more smaller instances of thesame problem. For example, if the original input is a skreeble with n glurps, theinput to each recursive call should be a skreeble with strictly less than n glurps.
Of course this is impossible if the skreeble has no glurps at all—You can’t havenegative glurps; that would be silly!—so in that case we must grindlebloff theskreeble using some other method.
We’ve already seen one instance of this pattern in the peasant multiplication
algorithm, which is based directly on the following recursive identity.
8>
if x = 0<0x · y = bx/2c · ( y + y)
if x is even>:bx/2c · ( y + y) + y if x is odd
The same recurrence can be expressed algorithmically as follows:PM(x, y):
if x = 0
return 0
else
x0
bx/2c
y0
y+y
prod PM
if x is odd
prod prod + yreturn prod

(x 0 , y 0 )hhRecurse!ii

A lazy Egyptian scribe could execute this algorithm by computing x 0 and y 0 ,asking a more junior scribe to multiply x 0 and y 0 , and then possibly adding y
to the junior scribe’s response. The junior scribe’s problem is simpler because
x 0 < x, and repeatedly decreasing a positive integer eventually leads to 0. How
the junior scribe actually computes x 0 · y 0 is none of the senior scribe’s business(and it’s none of your business, either).
When I was an undergraduate, I attributed recursion to “elves” instead of the Recursion Fairy,referring to the Brothers Grimm story about an old shoemaker who leaves his work unfinishedwhen he goes to bed, only to discover upon waking that elves (“Wichtelmänner”) have finishedeverything overnight. Someone more entheogenically experienced than I might recognize these
Rekursionswichtelmänner as Terence McKenna’s “self-transforming machine elves”.

���. R��������

�.�

Tower of Hanoi

The Tower of Hanoi puzzle was first published—as an actual physical puzzle!—by
the French teacher and recreational mathematician Édouard Lucas in,under the pseudonym “N. Claus (de Siam)” (an anagram of “Lucas d’Amiens”).
The following year, Henri de Parville described the puzzle with the following
remarkable story:In the great temple at Benares . . . beneath the dome which marks the centre of
the world, rests a brass plate in which are �xed three diamond needles, eacha cubit high and as thick as the body of a bee. On one of these needles, at thecreation, God placed sixty-four discs of pure gold, the largest disc resting on thebrass plate, and the others getting smaller and smaller up to the top one. This is
the Tower of Bramah. Day and night unceasingly the priests transfer the discs
from one diamond needle to another according to the �xed and immutablelaws of Bramah, which require that the priest on duty must not move morethan one disc at a time and that he must place this disc on a needle so that
there is no smaller disc below it. When the sixty-four discs shall have been thustransferred from the needle on which at the creation God placed them to oneof the other needles, tower, temple, and Brahmins alike will crumble into dust,
and with a thunderclap the world will vanish.

Figure �.�. The (8-disk) Tower of Hanoi puzzle

Of course, as good computer scientists, our first instinct on reading thisstory is to substitute the variable n for the hardwired constant 64. And because
most physical instances of the puzzle are made of wood instead of diamonds
and gold, I will call the three possible locations for the disks “pegs” instead ofLucas later claimed to have invented the puzzle in.
This English translation is taken from W. W. Rouse Ball’s
book Mathematical Recreations
and Essays.
The “great temple at Benares” is almost certainly the Kashi Vishvanath Temple in Varanasi,
Uttar Pradesh, India, located approximately
km west-north-west of Hà Nô.i, Viê.t Nam, where
the fictional N. Claus supposedly resided. Coincidentally, the French Army invaded Hanoi in,the same year Lucas released his puzzle, ultimately leading to its establishment as the capital of
French Indochina.

���.�. Tower of Hanoi“needles”. How can we move a tower of n disks from one peg to another, using athird spare peg as an occasional placeholder, without ever placing a disk on topof a smaller disk?
As N. Claus (de Siam) pointed out in the pamphlet included with his puzzle,
the secret to solving this puzzle is to think recursively. Instead of trying to solve
the entire puzzle at once, let’s concentrate on moving just the largest disk. We
can’t move it at the beginning, because all the other disks are in the way. So
first we have to move those n 1 smaller disks to the spare peg. Once that’s
done, we can move the largest disk directly to its destination. Finally, to finish
the puzzle, we have to move the n 1 smaller disks from the spare peg to theirdestination.
recursionrecursion

Figure �.�. The Tower of Hanoi algorithm; ignore everything but the bottom disk.

So now all we have to figure out is how to—
NO!! STOP!!
That’s it! We’re done! We’ve successfully reduced the n-disk Tower of Hanoi
problem to two instances of the (n 1)-disk Tower of Hanoi problem, which
we can gleefully hand off to the Recursion Fairy—or to carry Lucas’s metaphor
further, to the junior monks at the temple. Our job is finished. If we didn’t trust
the junior monks, we wouldn’t have hired them; let them do their job in peace.
Our reduction does make one subtle but extremely important assumption:
There is a largest disk. Our recursive algorithm works for any positive numberof disks, but it breaks down when n = 0. We must handle that case using a
different method. Fortunately, the monks at Benares, being good Buddhists, arequite adept at moving zero disks from one peg to another in no time at all, by
doing nothing.

Figure �.�. The vacuous base case for the Tower of Hanoi algorithm. There is no spoon.

���. R��������

It may be tempting to think about how all those smaller disks move around—or more generally, what happens when the recursion is unrolled—but really,
don’t do it. For most recursive algorithms, unrolling the recursion is neither
necessary nor helpful. Our only task is to reduce the problem instance we’re
given to one or more simpler instances, or to solve the problem directly if sucha reduction is impossible. Our recursive Tower of Hanoi algorithm is triviallycorrect when n = 0. For any n 1, the Recursion Fairy correctly moves the top
n 1 disks (more formally, the Inductive Hypothesis implies that our recursivealgorithm correctly moves the top n 1 disks) so our algorithm is correct.
The recursive Hanoi algorithm is expressed in pseudocode in Figure . .
The algorithm moves a stack of n disks from a source peg (src) to a destinationpeg (dst) using a third temporary peg (tmp) as a placeholder. Notice that thealgorithm correctly does nothing at all when n = 0.
H(n, src, dst, tmp):
if n > 0H(n 1, src, tmp, dst) hhRecurse!ii
move disk n from src to dst
H(n 1, tmp, dst, src) hhRecurse!ii

Figure �.�. A recursive algorithm to solve the Tower of Hanoi

Let T (n) denote the number of moves required to transfer n disks—the
running time of our algorithm. Our vacuous base case implies that T (0) = 0,
and the more general recursive algorithm implies that T (n) = 2T (n 1) + 1
for any n 1. By writing out the first several values of T (n), we can easily
guess that T (n) = 2n 1; a straightforward induction proof implies that thisguess is correct. In particular, moving a tower ofdisks requires 264 1 =
,
,
,
,
, ,
individual moves. Thus, even at the impressive rateof one move per second, the monks at Benares will be at work for approximately
billion years (“plus de cinq milliards de siècles”) before tower, temple, andBrahmins alike will crumble into dust, and with a thunderclap the world will
vanish.

�.�

Mergesort

Mergesort is one of the earliest algorithms designed for general-purpose storedprogram computers. The algorithm was developed by John von Neumann in, and described in detail in a publication with Herman Goldstine in, as
one of the first non-numerical programs for the EDVAC.
Goldstine and von Neumann actually described an non-recursive variant now usually called
bottom-up mergesort. At the time, large data sets were sorted by special-purpose machines—
almost all built by IBM—that manipulated punched cards using variants of binary radix sort. Von

�6�.�. Mergesort. Divide the input array into two subarrays of roughly equal size.
. Recursively mergesort each of the subarrays.
. Merge the newly-sorted subarrays into a single sorted array.
Input:
Divide:Recurse Left:
Recurse Right:
Merge:

S
S
I
I
A

O
O
N
N
E

R
R
O
O
G

T
T
R
R
I

I
I
S
S
L

N
N
T
T
M

G
G
G
A
N

E
E
E
E
O

X
X
X
G
P

A
A
A
L
R

M
M
M
M
S

P
P
P
P
T

L
L
L
X
X

Figure �.�. A mergesort example.

The first step is completely trivial—just divide the array size by two—and
we can delegate the second step to the Recursion Fairy. All the real work isdone in the final merge step. A complete description of the algorithm is given in
Figure . ; to keep the recursive structure clear, I’ve extracted the merge step
into an independent subroutine. The merge algorithm is also recursive—identify
the first element of the output array, and then recursively merge the rest of the
input arrays.
M

MS
if n > 1m
M
M
M(A[1 .. n]):bn/2cS(A[1 .. m])
hhRecurse!ii
S(A[m + 1 .. n]) hhRecurse!ii(A[1 .. n], m)(A[1 .. n], m):
i
1; j
m+1
for k
1 to nif j > nB[k] A[i]; ielse if i > m
B[k] A[ j]; jelse if A[i] < A[ j]B[k] A[i]; ielse
B[k] A[ j]; j

i+1
j+1
i+1
j+1

for k
1 to nA[k]B[k]Figure �.6. Mergesort

Correctness
To prove that this algorithm is correct, we apply our old friend induction twice,first to the M
subroutine then to the top-level M
algorithm.
Lemma �.�. M
correctly merges the subarrays A[1 .. m] and A[m + 1 .. n],assuming those subarrays are sorted in the input.
Neumann argued (successfully!) that because the EDVAC could sort faster than IBM’s dedicatedsorters, “without human intervention or need for additional equipment”, the EDVAC was an “allpurpose” machine, and special-purpose sorting machines were no longer necessary.

���. R��������

Proof: Let A[1 .. n] be any array and m any integer such that the subarrays
A[1 .. m] and A[m + 1 .. n] are sorted. We prove that for all k from 0 to n, the lastn k 1 iterations of the main loop correctly merge A[i .. m] and A[ j .. n] intoB[k .. n]. The proof proceeds by induction on n k + 1, the number of elements
remaining to be merged.
If k > n, the algorithm correctly merges the two empty subarrays by doing
absolutely nothing. (This is the base case of the inductive proof.) Otherwise,
there are four cases to consider for the kth iteration of the main loop.
• If j > n, then subarray A[ j .. n] is empty, so min A[i .. m] [ A[ j .. n] = A[i].

• If i > m, then subarray A[i .. m] is empty, so min A[i .. m] [ A[ j .. n] = A[ j].
• Otherwise, if A[i] < A[ j], then min A[i .. m] [ A[ j .. n] = A[i].

• Otherwise, we must have A[i] A[ j], and min A[i .. m] [ A[ j .. n] = A[ j].
In all four cases, B[k] is correctly assigned the smallest element of A[i .. m] [A[ j .. n]. In the two cases with the assignment B[k] A[i], the Recursion Fairy
correctly merges—sorry, I mean the Induction Hypothesis implies that the lastn k iterations of the main loop correctly merge A[i + 1 .. m] and A[ j .. n] intoB[k + 1 .. n]. Similarly, in the other two cases, the Recursion Fairy also correctly
merges the rest of the subarrays.
É
Theorem �.�. M

Scorrectly sorts any input array A[1 .. n].

Proof: We prove the theorem by induction on n. If n  1, the algorithm
correctly does nothing. Otherwise, the Recursion Fairy correctly sorts—sorry, I
mean the induction hypothesis implies that our algorithm correctly sorts thetwo smaller subarrays A[1 .. m] and A[m + 1 .. n], after which they are correctlyM
d into a single sorted array (by Lemma . ).
É

Analysis
Because the M
S
algorithm is recursive, its running time is naturally
expressed as a recurrence. M
clearly takes O(n) time, because it’s a simple
for-loop with constant work per iteration. We immediately obtain the following
recurrence for M
S:
T (n) = T dn/2e + T bn/2c + O(n).

As in most divide-and-conquer recurrences, we can safely strip out the floors
and ceilings (using a technique called domain transformations described laterin this chapter), giving us the simpler recurrence T (n) = 2T (n/2) + O(n). The“all levels equal” case of the recursion tree method (also described later in thischapter) immediately implies the closed-form solution T (n) = O(n log n). Even
if you are not (yet) familiar with recursion trees, you can verify the solution
T (n) = O(n log n) by induction.
�8�.�. Quicksort

�.� Quicksort
Quicksort is another recursive sorting algorithm, discovered by Tony Hoare in
and first published in. In this algorithm, the hard work is splitting
the array into smaller subarrays before recursion, so that merging the sorted
subarrays is trivial.
. Choose a pivot element from the array.
. Partition the array into three subarrays containing the elements smaller
than the pivot, the pivot element itself, and the elements larger than thepivot.
. Recursively quicksort the first and last subarrays.
Input:
Choose a pivot:
Partition:
Recurse Left:
Recurse Right:

S
S
A
A
A

O
O
G
E
E

R
R
O
G
G

T
T
E
I
I

I
I
I
L
L

N
N
N
M
M

G
G
L
N
N

E
E
M
O
O

X
X
P
P
P

A
A
T
T
R

M
M
X
X
S

P
P
S
S
T

L
L
R
R
X

Figure �.�. A quicksort example.

More detailed pseudocode is given in Figure . . In the P
subroutine,
the input parameter p is the index of the pivot element in the unsorted array;the subroutine partitions the array and returns the new index of the pivot
element. There are many different efficient partitioning algorithms; the one
I’m presenting here is attributed to Nico Lomuto. The variable ` counts thenumber of items in the array that are `ess than the pivot element.
P
Q

S(A[1 .. n]):
if (n > 1)
Choose a pivot element A[p]rP(A, p)Q
S(A[1 .. r 1]) hhRecurse!ii
Q
S(A[r + 1 .. n]) hhRecurse!ii(A[1 .. n], p):swap A[p] $ A[n]` 0hh#items < pivotii
for i

1 to n 1
if A[i] < A[n]` `+1swap A[`] $ A[i]swap A[n] $ A[` + 1]
return ` + 1

Figure �.8. Quicksort

Correctness
Just like mergesort, proving that Q
induction proofs: one to prove that P

S

is correct requires two separate
correctly partitions the array, andHoare proposed a more complicated “two-way” partitioning algorithm that has some
practical advantages over Lomuto’s algorithm. On the other hand, Hoare’s partitioning algorithm
is one of the places off-by-one errors go to die.

���. R��������

the other to prove that Q
S
correctly sorts assuming P
is correct.
To prove P
is correct, we need to prove the following loop invariant: At
the end of each iteration of the main loop, everything in the subarray A[1 .. `]is `ess than A[n], and nothing in the subarray A[` + 1 .. i] is less than A[n].
I’ll leave the remaining straightforward but tedious details as exercises for thereader.

Analysis
The analysis of quicksort is also similar to that of mergesort. P
clearlyruns in O(n) time, because it’s a simple for-loop with constant work per iteration.
For Q
S, we get a recurrence that depends on r, the rank of the chosenpivot element:
T (n) = T (r 1) + T (n r) + O(n)If we could somehow always magically choose the pivot to be the median elementof the array A, we would have r = dn/2e, the two subproblems would be as close
to the same size as possible, the recurrence would become
T (n) = T dn/2e

1 + T bn/2c + O(n)  2T (n/2) + O(n),and we’d have T (n) = O(n log n) using either the recursion tree method or
the even simpler “Oh yeah, we already solved that recurrence for mergesort”
method.
In fact, as we will see later in this chapter, we can actually locate themedian element in an unsorted array in linear time, but the algorithm is fairly
complicated, and the hidden constant in the O(·) notation is large enough tomake the resulting sorting algorithm impractical. In practice, most programmers
settle for something simple, like choosing the first or last element of the array.
In this case, r can take any value between 1 and n, so we haveT (n) = max T (r1rn1) + T (nr) + O(n) .

In the worst case, the two subproblems are completely unbalanced—either r = 1
or r = n—and the recurrence becomes T (n)  T (n 1) + O(n). The solution is
T (n) = O(n 2 ).
Another common heuristic is called “median of three”—choose three elements (usually at the beginning, middle, and end of the array), and takethe median of those three elements as the pivot. Although this heuristic issomewhat more efficient in practice than just choosing one element, especiallywhen the array is already (nearly) sorted, we can still have r = 2 or r = n 1
in the worst case. With the median-of-three heuristic, the recurrence becomesT (n)  T (1) + T (n 2) + O(n), whose solution is still T (n) = O(n2 ).
���.6. The Pattern

Intuitively, the pivot element should “usually” fall somewhere in the middle of
the array, say with rank between n/10 and 9n/10. This observation suggests thatthe “average-case” running time should be O(n log n). Although this intuition
can be formalized, the most common formalization makes the completely
unrealistic assumption that all permutations of the input array are equally likely.
Real world data may be random, but it is not random in any way that we canpredict in advance, and it is certainly not uniform!
Occasionally people also consider “best case” running time for some reason.
We won’t.

�.6

The Pattern

Both mergesort and quicksort follow a general three-step pattern called divideand conquer:. Divide the given instance of the problem into several independent smaller
instances of exactly the same problem.
. Delegate each smaller instance to the Recursion Fairy.
. Combine the solutions for the smaller instances into the final solution
for the given instance.
If the size of any instance falls below some constant threshold, we abandon
recursion and solve the problem directly, by brute force, in constant time.
Proving a divide-and-conquer algorithm correct almost always requires
induction. Analyzing the running time requires setting up and solving arecurrence, which usually (but unfortunately not always!) can be solved using
recursion trees.

�.�

Recursion Trees

So what are these “recursion trees” I keep talking about? Recursion trees area simple, general, pictorial tool for solving divide-and-conquer recurrences. A
recursion tree is a rooted tree with one node for each recursive subproblem. The
value of each node is the amount of time spent on the corresponding subproblem
excluding recursive calls. Thus, the overall running time of the algorithm is thesum of the values of all nodes in the tree.
To make this idea more concrete, imagine a divide-and-conquer algorithm
that spends O( f (n)) time on non-recursive work, and then makes r recursive
On the other hand, if we choose the pivot index p uniformly at random, then Q
runs
in O(n log n) time with high probability, for every possible input array. The key difference is thatthe randomness is controlled by our algorithm, not by the All-Powerful Malicious Adversary whogives us input data after reading our code. The analysis of randomized quicksort is unfortunately
outside the scope of this book, but you can find relevant lecture notes at http://algorithms.wtf/.

���. R��������

calls, each on a problem of size n/c. Up to constant factors (which we canhide in the O( ) notation), the running time of this algorithm is governed by therecurrence
T (n) = r T (n/c) + f (n).
The root of the recursion tree for T (n) has value f (n) and r children,each of which is the root of a (recursively defined) recursion tree for T (n/c).
Equivalently, a recursion tree is a complete r-ary tree where each node at depth dcontains the value f (n/c d ). (Feel free to assume that n is an integer power of c,so that n/c d is always an integer, although in fact this doesn’t matter.)
In practice, I recommend drawing out the first two or three levels of thetree, as in Figure . .

f(n/c)

f(n)

f(n)

r

+

f(n/c)

rf(n/c²)f(n/c²)f(n/c²)f(n/c²)f(n/c)rr

f(n/c²)f(n/c²)f(n/c²)f(n/c²)r ⋅ f(n/c)

f(n/c)

rf(n/c²)f(n/c²)f(n/c²)f(n/c²)f(n/c²)f(n/c²)f(n/c²)f(n/c²)+r² ⋅ f(n/c²)
+

+
L
L
L
L
L
L
L
L
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
L))
L))
L))
L))
L))
L))
L))
L))
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
L)
L)
L)
L)
L)
L)
L)
L)
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
L)
L)
L)
L)
L)
L)
L)
L)
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
L
L
L
L
L
L
L
L
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
f(n/c
L)
L)
L)
L)
L)
L)
L)
L)
f(n/c
)
f(n/c
)
f(n/c
)
f(n/c
)
f(n/c
)
f(n/c
)
f(n/c
)
f(n/c
L
L
L
L
L
L
L
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/cL))rL ⋅ f(n/cL)

Figure �.�. A recursion tree for the recurrence T (n) = r T (n/c) + f (n)The leaves of the recursion tree correspond to the base case(s) of therecurrence. Because we’re only looking for asymptotic bounds, the precise basecase doesn’t actually matter; we can safely assume T (n) = 1 for all n  n0 ,where n0 is an arbitrary positive constant. In particular, we can choose whatevervalue of n0 is most convenient for our analysis. For this example, I’ll choosen0 = 1.
Now T (n) is the sum of all values in the recursion tree; we can evaluate thissum by considering the tree level-by-level. For each integer i, the ith level ofthe tree has exactly r i nodes, each with value f (n/c i ). Thus,
T (n) =

LX
i=0

r i · f (n/c i )(⌃)

where L is the depth of the tree. Our base case n0 = 1 immediately implies
L = logc n, because n/c L = n0 = 1. It follows that the number of leaves in���.�. Recursion Trees

the recursion tree is exactly r L = r logc n = nlogc r . Thus, the last term in thelevel-by-level sum (⌃) is nlogc r · f (1) = O(nlogc r ), because f (1) = O(1).
There are three common cases where the level-by-level series (⌃) is especiallyeasy to evaluate:• Decreasing: If the series decays exponentially—every term is a constantfactor smaller than the previous term—then T (n) = O( f (n)). In this case,the sum is dominated by the value at the root of the recursion tree.
• Equal: If all terms in the series are equal, we immediately have T (n) =O( f (n)· L) = O( f (n) log n). (The constant c vanishes into the O( ) notation.)• Increasing: If the series grows exponentially—every term is a constant factor
larger than the previous term—then T (n) = O(nlogc r ). In this case, the sum
is dominated by the number of leaves in the recursion tree.
In the first and third cases, only the largest term in the geometric series matters;
all other terms are swallowed up by the O(·) notation. In the decreasing case,
we don’t even have to compute L; the asymptotic upper bound would still holdif the recursion tree were infinite!
As an elementary example, if we draw out the first few levels of the recursion
tree for the (simplified) mergesort recurrence T (n) = 2T (n/2) + O(n), we
discover that all levels are equal, which immediately implies T (n) = O(n log n).
n
n/2
n/4
n/8

n/8

n/2
n/4

n/8

n/8

n/4
n/8

n/8

n/4
n/8

n/8

Figure �.��. The recursion tree for mergesort

The recursion tree technique can also be used for algorithms where therecursive subproblems have different sizes. For example, if we could somehow
implement quicksort so that the pivot always lands in the middle third of thesorted array, the worst-case running time would satisfy the recurrence
T (n)  T (n/3) + T (2n/3) + O(n).
This recurrence might look scary, but it’s actually pretty tame. If we drawout a few levels of the resulting recursion tree, we quickly realize that thesum of values on any level is at most n—deeper levels might be missing somenodes—and the entire tree has depth log3/2 n = O(log n). It immediately follows
that T (n) = O(n log n). (Moreover, the number of full levels in the recursion
���. R��������

tree is log3 n = ⌦(log n), so this conservative analysis can be improved by atmost a constant factor, which for our purposes means not at all.) The fact thatthe recursion tree is unbalanced simply doesn’t matter.
As a more extreme example, the worst-case recurrence for quicksort T (n) =T (n 1) + T (1) + O(n) gives us a completely unbalanced recursion tree, where
one child of each internal node is a leaf. The level-by-level sum doesn’t fall
into any of our three default categories, but we can still derive the solution
T (n) = O(n2 ) by observing that every level value is at most n and there are at
most n levels. (Again, this conservative analysis is tight, because n/2 levels eachhave value at least n/2.)
n

n

n/3
n/9

2n/3
2n/9

2n/9

n–1
4n/9

n–2
n–3

1
1

1

Figure �.��. Recursion trees for quicksort with good pivots (left) and with worst-case pivots (right)™Ignoring Floors and Ceilings Is Okay, Honest

Careful readers might object that our analysis brushes an important detail under
the rug. The running time of mergesort doesn’t really obey the recurrence
T (n) = 2T (n/2) + O(n); after all, the input size n might be odd, and what could
it possibly mean to sort an array of size 42 12 or 17 78 ? The actual mergesort
recurrence is somewhat messier:T (n) = T dn/2e + T bn/2c + O(n).

Sure, we could check that T (n) = O(n log n) using induction, but the necessary
calculations would be awful. Fortunately, there is a simple technique forremoving floors and ceilings from recurrences, called domain transformation.
• First, because we are deriving an upper bound, we can safely overestimate
T (n), once by pretending that the two subproblem sizes are equal, andagain to eliminate the ceiling:
T (n)  2T dn/2e + n  2T (n/2 + 1) + n.

Formally, we are treating T as a function over the reals, not just over the integers, thatsatisfies the given recurrence with the base case T (n) = C for all n  n0 , for some real numbers
C 0 and n0 > 0 whose values don’t matter. If n happens to be an integer, then T (n) coincides
with the running time of an algorithm on an input of size n, but that doesn’t matter, either.

��™�.8. Linear-Time Selection• Second, we define a new function S(n) = T (n + ↵), choosing the constant ↵so that S(n) satisfies the simpler recurrence S(n)  2S(n/2) + O(n). To
find the correct constant ↵, we derive a recurrence for S from our given
recurrence for T :S(n) = T (n + ↵)[definition of S] 2T (n/2 + ↵/2 + 1) + n + ↵= 2S(n/2↵/2 + 1) + n + ↵[recurrence for T ][definition of S]

Setting ↵ = 2 simplifies this recurrence to S(n)  2S(n/2) + n + 2, which isexactly what we wanted.
• Finally, the recursion tree method implies S(n) = O(n log n), and therefore
T (n) = S(n2) = O((n2) log(n2)) = O(n log n),exactly as promised.
Similar domain transformations can be used to remove floors, ceilings, and evenlower order terms from any divide and conquer recurrence. But now that werealize this, we don’t need to bother grinding through the details ever again!
From now on, faced with any divide-and-conquer recurrence, I will silently
brush floors and ceilings and lower-order terms under the rug, and I encourage
you to do the same.
™�.8

Linear-Time Selection

During our discussion of quicksort, I claimed in passing that we can find the
median of an unsorted array in linear time. The first such algorithm was
discovered by Manuel Blum, Bob Floyd, Vaughan Pratt, Ron Rivest, and Bob
Tarjan in the earlys. Their algorithm actually solves the more general
problem of selecting the kth smallest element in an n-element array, given thearray and the integer k as input, using a variant of an algorithm called quickselector one-armed quicksort. Quickselect was first described by Tony Hoare in,
literally on the same page where he first published quicksort.

QuickselectThe generic quickselect algorithm chooses a pivot element, partitions the arrayusing the same P
subroutine as Q
S
, and then recursively
searches only one of the two subarrays, specifically, the one that contains thekth smallest element of the original input array. Pseudocode for quickselect isgiven in Figure . .
���. R��������Q

S(A[1 .. n], k):
if n = 1
return A[ ]elseChoose a pivot element A[p]rP
(A[1 .. n], p)if k < rreturn Q
S
else if k > r
return Q
S
else
return A[r](A[1 .. r1], k)(A[r + 1 .. n], kr)

Figure �.��. Quickselect, or one-armed quicksort

This algorithm has two important features. First, just like quicksort, thecorrectness of quickselect does not depend on how the pivot is chosen. Second,even if we really only care about selecting medians (the special case k = n/2),
Hoare’s recursive strategy requires us to consider the more general selection
problem; the median of the input array A[1 .. n] is almost never the median ofeither of the two smaller subarrays A[1 .. r 1] or A[r + 1 .. n].
The worst-case running time of Q
S
obeys a recurrence similar to
Q
S. We don’t know the value of r, or which of the two subarrays we’llrecursively search, so we have to assume the worst.
T (n)  max max {T (r1rn1), T (nr)} + O(n)We can simplify the recurrence slightly by letting ` denote the length of therecursive subproblem:
T (n) max T (`) + O(n)0`n 1

If the chosen pivot element is always either the smallest or largest element in
the array, the recurrence simplifies to T (n) = T (n 1) + O(n), which implies
T (n) = O(n2 ). (The recursion tree for this recurrence is just a simple path.)

Good pivots
We could avoid this quadratic worst-case behavior if we could somehow magicallychoose a good pivot, meaning `  ↵n for some constant ↵ < 1. In this case, therecurrence would simplify to
T (n)  T (↵n) + O(n).
�6™�.8. Linear-Time Selection

This recurrence expands into a decreasing geometric series, which is dominatedby its largest term, so T (n) = O(n). (Again, the recursion tree is just a simple
path. The constant in the O(n) running time depends on the constant ↵.)In other words, if we could somehow quickly find an element that’s evenclose to the median in linear time, we could find the exact median in linear
time. So now all we need is an Approximate Median Fairy. The Blum-FloydPratt-Rivest-Tarjan algorithm chooses a good quickselect pivot by recursively
computing the median of a carefully-chosen subset of the input array. The
Approximate Median Fairy is just the Recursion Fairy in disguise!
Specifically, we divide the input array into dn/5e blocks, each containing
exactly 5 elements, except possibly the last. (If the last block isn’t full, just throw
in a few 1s.) We compute the median of each block by brute force, collectthose medians into a new array M [1 .. dn/5e], and then recursively computethe median of this new array. Finally, we use the median of the block medians(called “mom” in the pseudocode below) as the quickselect pivot.
M

S(A[1 .. n], k):
if n  25 hhor whateverii
use brute force
else
m
dn/5e
for i
1 to mM[i]M�����O�F���(A[5i 4 .. 5i]) hhBrute force!ii
mom M��S�����(M[1 .. m], bm/2c)
hhRecursion!iirP(A[1 .. n], mom)

if k < rreturn M S
else if k > r
return M S
else
return mom(A[1 .. rhhRecursion!ii

1], k)(A[r + 1 .. n], kr)hhRecursion!ii

M S
uses recursion for two different purposes; the first time tochoose a pivot element (mom), and the second time to search through theentries on one side of that pivot.

Analysis
But why is this fast? The first key⌅ insight⇧ is that the median of medians is agood pivot. Mom is larger than dn/5e/2
1 ⇡ n/10 block medians, and eachblock median is larger than two other elements in its block. Thus, mom is bigger
than at least 3n/10 elements in the input array; symmetrically, mom is smaller
than at least 3n/10 elements. Thus, in the worst case, the second recursive callsearches an array of size at most 7n/10.
���. R��������

We can visualize the algorithm’s behavior by drawing the input array as a
5 ⇥ dn/5e grid, which each column represents five consecutive elements. For
purposes of illustration, imagine that we sort every column from top down, andthen we sort the columns by their middle element. (Let me emphasize that thealgorithm does not actually do this!) In this arrangement, the median-of-medians
is the element closest to the center of the grid.

The left half of the first three rows of the grid contains 3n/10 elements, eachof which is smaller than mom. If the element we’re looking for is larger thanmom, our algorithm will throw away everything smaller than mom, including
those 3n/10 elements, before recursing. Thus, the input to the recursive
subproblem contains at most 7n/10 elements. A symmetric argument implies
that if our target element is smaller than mom, we discard at least 3n/10
elements larger than mom, so the input to our recursive subproblem has at most
7n/10 elements.

Okay, so mom is a good pivot, but our algorithm still makes two recursive
calls instead of just one; how do we prove linear time? The second key insight isthat the total size of the two recursive subproblems is a constant factor smaller
than the size of the original input array. The worst-case running time of thealgorithm obeys the recurrence
T (n)  T (n/5) + T (7n/10) + O(n).
If we draw out the recursion tree for this recurrence, we observe that the total
work at each level of the recursion tree is at most 9/10 the total work at theprevious level. Thus, the level sums decay exponentially, giving us the solution
T (n) = O(n). (Again, the fact that the recursion tree is unbalanced is completely
immaterial.) Hooray! Thanks, Mom!

�8

™�.8. Linear-Time Selection

n
n/5
n/25

n
7n/10

7n/50

7n/50

Figure �.��. The recursion trees for M

49n/100

S

n/3
n/9

2n/3
2n/9

2n/9

4n/9

and a similar selection algorithm with blocks of size �

Sanity Checking
At this point, many students ask about that magic constant 5. Why did wechoose that particular block size? The answer is that 5 is the smallest odd
block size that gives us exponential decay in the recursion-tree analysis! (Evenblock sizes introduce additional complications.) If we had used blocks of size 3
instead, the running-time recurrence would be
T (n)  T (n/3) + T (2n/3) + O(n).

We’ve seen this recurrence before! Every level of the recursion tree has total
value at most n, and the depth of the recursion tree is log3/2 n = O(log n), so
the solution to this recurrence is T (n)  O(n log n). (Moreover, this analysis istight, because the recursion tree has log3 n complete levels.) Median-of-mediansselection using 3-element blocks is no faster than sorting.
Finer analysis reveals that the constant hidden by the O( ) notation is quite
large, even if we count only comparisons. Selecting the median of 5 elements
requires at most 6 comparisons, so we need at most 6n/5 comparisons to set
up the recursive subproblem. Naïvely partitioning the array after the recursive
call would require n 1 comparisons, but we already know 3n/10 elements
larger than the pivot and 3n/10 elements smaller than the pivot, so partitioning
actually requires only 2n/5 additional comparisons. Thus, a more precise
recurrence for the worst-case number of comparisons is
T (n)  T (n/5) + T (7n/10) + 8n/5.

The recursion tree method implies the upper boundÅ ã
8n X 9 i 8n
T (n) =· 10 = 16n.
5 i 0 10
5
In practice, median-of-medians selection is not as slow as this worst-case analysis
predicts—getting a worst-case pivot at every level of recursion is incredibly
unlikely—but it is still slower than sorting for even moderately large arrays.
In fact, the right way to choose the pivot element in practice is to choose it uniformly at
random. Then the expected number of comparisons required to find the median is at most 4n.
See my randomized algorithms lecture notes at http://algorithms.wtf for more details.

���. R��������

�.�

Fast Multiplication

In the previous chapter, we saw two ancient algorithms for multiplying two
n-digit numbers in O(n2 ) time: the grade-school lattice algorithm and the
Egyptian peasant algorithm.
Maybe we can get a more efficient algorithm by splitting the digit arrays inhalf and exploiting the following identity:(10m a + b)(10m c + d) = 102m ac + 10m (bc + ad) + bd
This recurrence immediately suggests the following divide-and-conquer algorithm to multiply two n-digit numbers x and y. Each of the four sub-productsac, bc, ad, and bd is computed recursively, but the multiplications in the lastline are not recursive, because we can multiply by a power of ten by shifting thedigits to the left and filling in the correct number of zeros, all in O(n) time.
SM(x, y, n):
if n = 1
return x · yelse
m dn/2eabx/10m c; b
x mod 10mcb y/10m c; dy mod 10meS
M(a, c, m)fSM(b, d, m)gSM(b, c, m)h S
M(a, d, m)
2m
m
return 10 e + 10 (g + h) + f

hhx = 10m a + bii
hh y = 10m c + dii

Correctness of this algorithm follows easily by induction. The running time forthis algorithm follows the recurrence
T (n) = 4T (dn/2e) + O(n).
The recursion tree method transforms this recurrence into an increasing geometric series, which implies T (n) = O(nlog2 4 ) = O(n2 ). In fact, this algorithm
multiplies each digit of x with each digit of y, just like the lattice algorithm.
So I guess that didn’t work. Too bad. It was a nice idea.
In the mids, Andrei Kolmogorov, one of the giants of th century
mathematics, publicly conjectured that there is no algorithm to multiply two
n-digit numbers in subquadratic time. Kolmogorov organized a seminar at
Moscow University in, where he restated his “n2 conjecture” and posedseveral related problems that he planned to discuss at future meetings. Almost
exactly a week later, a -year-old student named Anatoliı̆ Karatsuba presented
Kolmogorov with a remarkable counterexample. According to Karatsuba himself,���.�. Fast Multiplication

n
n/2

n/2

n/2

n/2

n/4 n/4 n/4 n/4n/4 n/4 n/4 n/4n/4 n/4 n/4 n/4n/4 n/4 n/4 n/4

Figure �.��. The recursion tree for naïve divide-and-conquer multiplication

After the seminar I told Kolmogorov about the new algorithm and about thedisproof of the n2 conjecture. Kolmogorov was very agitated because thiscontradicted his very plausible conjecture. At the next meeting of the seminar, Kolmogorov himself told the participants about my method, and at thatpoint the seminar was terminated.

Karatsuba observed that the middle coefficient bc +ad can be computed from theother two coefficients ac and bd using only one more recursive multiplication,
via the following algebraic identity:
ac + bd(ab)(cd) = bc + ad

This trick lets us replace the four recursive calls in the previous algorithm with
only three recursive calls, as shown below:FM(x, y, n):
if n = 1
return x · yelse
m dn/2eabx/10m c; b
x mod 10m
hhx = 10m a + biimmcb y/10 c; dy mod 10hh y = 10m c + diieF M(a, c, m)f
F M(b, d, m)g
F M(a b, c d, m)
return 102m e + 10m (e + f g) + f

The running time of Karatsuba’s FMalgorithm follows the recurrence

T (n)  3T (dn/2e) + O(n)Once again, the recursion tree method transforms this recurrence into anincreasing geometric series, but the new solution is only T (n) = O(nlog2 3 ) =O(n 1.58496 ), a significant improvement over our earlier quadratic time bound.
My presentation simplifies the actual history slightly. In fact, Karatsuba proposed analgorithm based on the formula (a + b)(c + d) ac bd = bc + ad. This algorithm also runsin O(nlg 3 ) time, but the actual recurrence is slightly messier: a b and c d are still m-digit
numbers, but a + b and c + d might each have m + 1 digits. The simplification presented here isdue to Donald Knuth.

���. R��������

Karatsuba’s algorithm arguably launched the design and analysis of algorithms
as a formal field of study.
n
n/2
n/4

n/4

n/2
n/4

n/4

n/4

n/2
n/4

n/4

n/4

n/4

Figure �.��. The recursion tree for Karatsuba’s divide-and-conquer multiplication algorithm

We can take Karatsuba’s idea even further, splitting the numbers into
more pieces and combining them in more complicated ways, to obtain evenfaster multiplication algorithms. Andrei Toom discovered an infinite familyof algorithms that split any integer into k parts, each with n/k digits, andthen compute the product using only 2k 1 recursive multiplications; Toom’s
algorithms were further simplified by Stephen Cook in his PhD thesis. For any
fixed k, the Toom-Cook algorithm runs in O(n1+1/(lg k) ) time, where the hidden
constant in the O(·) notation depends on k.
Ultimately, this divide-and-conquer strategy led Gauss (yes, really) to thediscovery of the Fast Fourier transform.
The basic FFT algorithm itself
runs in O(n log n) time; however, using FFTs for integer multiplication incurs
some small additional overhead. The first FFT-based integer multiplication
algorithm, published by Arnold Schönhage and Volker Strassen in, runsin O(n log n log log n) time. Schönhage-Strassen remained the theoreticallyfastest integer multiplication algorithm for several decades, before Martin Fürer
discovered the first of a long series of technical improvements. Finally, in,David Harvey and Joris van der Hoeven published an algorithm that runs inO(n log n) time.

�.��

Exponentiation

Given a number a and a positive integer n, suppose we want to compute a n . The
standard naïve method is a simple for-loop that performs n 1 multiplications
by a:
See http://algorithms.wtf for lecture notes on Fast Fourier transforms.
Schönhage-Strassen is actually the fastest algorithm in practice for multiplying integers withmore than about
digits; the more recent algorithms of Fürer, Harvey, van der Hoeven, andothers would be faster “in practice” only for integers with more digits than there are particles in
the universe.

���.��. ExponentiationSP(a, n):xafor i
2 to nxx ·areturn x

This iterative algorithm requires n multiplications.
The input parameter a could be an integer, or a rational, or a floating point
number. In fact, it doesn’t need to be a number at all, as long as it’s somethingthat we know how to multiply. For example, the same algorithm can be used
to compute powers modulo some finite number (an operation commonly usedin cryptography algorithms) or to compute powers of matrices (an operation
used to evaluate recurrences and to compute shortest paths in graphs). Because
we don’t know what kind of object we’re multiplying, we can’t know how muchtime a single multiplication requires, so we’re forced to analyze the running
time in terms of the number of multiplications.
There is a much faster divide-and-conquer method, originally proposed by
the Indian prosodist Piṅgala in the nd century, which uses the following
simple recursive formula:8>
if n = 0<1
an =(a n/2 )2>:(abn/2c )2 · a

if n > 0 and n is evenotherwiseP ˙P(a, n):
if n = 1
return a
else
x
P ˙
P
(a, bn/2c)
if n is evenreturn x · xelse
return x · x · a

The total number of multiplications performed by this algorithm satisfies therecurrence T (n)  T (n/2) + 2. The recursion-tree method immediately give us
the solution T (n) = O(log n).
A nearly identical exponentiation algorithm can also be derived directlyfrom the Egyptian peasant multiplication algorithm from the previous chapter,by replacing addition with multiplication (and in particular, replacing duplation
with squaring).
8>
if n = 0<1n
2 n/2
a = (a )if n > 0 and n is even>:(a2 )bn/2c · a otherwise���. R��������

PP(a, n):
if n = 1
return aelse if n is evenreturn P
P
else
return PP(a2 , n/2)
(a2 , bn/2c) · a

This algorithm—which might reasonably be called “squaring and mediation”—
also performs only O(log n) multiplications.
Both of these algorithms are asymptotically optimal; any algorithm thatcomputes a n must perform at least ⌦(log n) multiplications, because each
multiplication at most doubles the largest power computed so far. In fact,
when n is a power of two, both of these algorithms require exactly log2 nmultiplications, which is exactly optimal. However, there are slightly fastermethods for other values of n. For example, P ˙
P
and P
P
each compute a15 using six multiplications, but in fact only five multiplications
are necessary:• Piṅgala: a ! a2 ! a3 ! a6 ! a7 ! a14 ! a15• Peasant: a ! a2 ! a4 ! a8 ! a12 ! a14 ! a15• Optimal: a ! a2 ! a3 ! a5 ! a10 ! a15

It is a long-standing open question whether the absolute minimum number ofmultiplications for a given exponent n can be computed efficiently.

Exercises
Tower of Hanoi. Prove that the original recursive Tower of Hanoi algorithm performs exactly
the same sequence of moves—the same disks, to and from the same pegs,
in the same order—as each of the following non-recursive algorithms. The
pegs are labeled 0, 1, and 2, and our problem is to move a stack of n disks
from peg 0 to peg 2 (as shown on page ).
(a) If n is even, swap pegs 1 and 2. At the ith step, make the only legal
move that avoids peg i mod 3. If there is no legal move, then all disks
are on peg i mod 3, and the puzzle is solved.
(b) For the first move, move disk 1 to peg 1 if n is even and to peg 2 if n isodd. Then repeatedly make the only legal move that involves a different
disk from the previous move. If no such move exists, the puzzle is solved.
(c) Pretend that disks n + 1, n + 2, and n + 3 are at the bottom of pegs 0, 1,
and 2, respectively. Repeatedly make the only legal move that satisfies
the following constraints, until no such move is possible.
��Exercises• Do not place an odd disk directly on top of another odd disk.
• Do not place an even disk directly on top of another even disk.
• Do not undo the previous move.
(d) Let ⇢(n) denote the smallest integer k such that n/2k is not an integer.
For example, ⇢(42) = 2, because 42/21 is an integer but 42/22 is not.
(Equivalently, ⇢(n) is one more than the position of the least significant 1
in the binary representation of n.) Because its behavior resembles themarks on a ruler, ⇢(n) is sometimes called the ruler function.
R

H
(n):
i
1
while ⇢(i)  n
if n i is evenmove disk ⇢(i) forwardelse
move disk ⇢(i) backwardi
i+1

hh0 ! 1 ! 2 ! 0ii
hh0 ! 2 ! 1 ! 0ii. The Tower of Hanoi is a relatively recent descendant of a much older
mechanical puzzle known as the Chinese linked rings, Baguenaudier, Cardan’s Rings, Meleda, Patience, Tiring Irons, Prisoner’s Lock, Spin-Out, andmany other names. This puzzle was already well known in both China
and Europe by the th century. The Italian mathematician Luca Pacioli
described the -ring puzzle and its solution in his unpublished treatise De
Viribus Quantitatis, written between
and; only a few years later,
the Ming-dynasty poet Yang Shen described the -ring puzzle as “a toy for
women and children”. The puzzle is apocryphally attributed to a nd-century
Chinese general, who gave the puzzle to his wife to occupy her time while
he was away at war.

Figure �.�6. The �-ring Baguenaudier, from Récréations Mathématiques by Édouard Lucas (�8��) (SeeImage Credits at the end of the book.)

De Viribus Quantitatis [On the Powers of Numbers] is an important early work on recreational
mathematics and perhaps the oldest surviving treatise on magic. Pacioli is better known for
Summa de Aritmetica, a near-complete encyclopedia of late th-century mathematics, which
included the first description of double-entry bookkeeping.

���. R��������

The Baguenaudier puzzle has many physical forms, but one of the mostcommon consists of a long metal loop and several rings, which are connected
to a solid base by movable rods. The loop is initially threaded through therings as shown in Figure . ; the goal of the puzzle is to remove the loop.
More abstractly, we can model the puzzle as a sequence of bits, one
for each ring, where the ith bit is 1 if the loop passes through the ith ringand 0 otherwise. (Here we index the rings from right to left, as shown in
Figure . .) The puzzle allows two legal moves:• You can always flip the 1st (= rightmost) bit.
• If the bit string ends with exactly z 0s, you can flip the (z + 2)th bit.
The goal of the puzzle is to transform a string of n 1s into a string of n 0s.
For example, the following sequence of 21 moves solves the -ring puzzle:
1

3

1

2

1

5

1

2

1

3

1

2

1

4

1

2

1

3

1

2

11111 ! 11110 ! 11010 ! 11011 ! 11001 ! 11000! 01000 ! 01001 ! 01011 ! 01010 ! 01110! 01111 ! 01101 ! 01100 ! 00100 ! 00101

1! 00111 ! 00110 ! 00010 ! 00011 ! 00001 ! 00000©

(a) Call a sequence of moves reduced if no move is the inverse of the previous
move. Prove that for any non-negative integer n, there is exactly one
reduced sequence of moves that solves the n-ring Baguenaudier puzzle.
[Hint: This problem is much easier if you’re already familiar withgraphs.](b) Describe an algorithm to solve the Baguenaudier puzzle. Your input isthe number of rings n; your algorithm should print a reduced sequenceof moves that solves the puzzle. For example, given the integer 5 as
input, your algorithm should print the sequence 1, 3, 1, 2, 1, 5, 1, 2, 1, 3,
1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1.
(c) Exactly how many moves does your algorithm perform, as a functionof n? Prove your answer is correct.
. A less familiar chapter in the Tower of Hanoi’s history is its brief relocationof the temple from Benares to Pisa in the early th century. The relocation
was organized by the wealthy merchant-mathematician Leonardo Fibonacci,
at the request of the Holy Roman Emperor Frederick II, who had heard
reports of the temple from soldiers returning from the Crusades. The Towersof Pisa and their attendant monks became famous, helping to establish Pisa
as a dominant trading center on the Italian peninsula.
Portions of this story are actually true.

�6

Exercises

Unfortunately, almost as soon as the temple was moved, one of the
diamond needles began to lean to one side. To avoid the possibility of
the leaning tower falling over from too much use, Fibonacci convinced thepriests to adopt a more relaxed rule: Any number of disks on the leaningneedle can be moved together to another needle in a single move. It was
still forbidden to place a larger disk on top of a smaller disk, and disks had tobe moved one at a time onto the leaning needle or between the two verticalneedles.

Figure �.��. The Towers of Pisa. In the �fth move, two disks are taken off the leaning needle.

Thanks to Fibonacci’s new rule, the priests could bring about the endof the universe somewhat faster from Pisa than they could from Benares.
Fortunately, the temple was moved from Pisa back to Benares after the
newly crowned Pope Gregory IX excommunicated Frederick II, making
the local priests less sympathetic to hosting foreign heretics with strange
mathematical habits. Soon afterward, a bell tower was erected on the spot
where the temple once stood; it too began to lean almost immediately.
Describe an algorithm to transfer a stack of n disks from one verticalneedle to the other vertical needle, using the smallest possible number ofmoves. Exactly how many moves does your algorithm perform?
. Consider the following restricted variants of the Tower of Hanoi puzzle Ineach problem, the pegs are numbered 0, 1, and 2, and your task is to movea stack of n disks from peg 0 to peg 2, exactly as in problem .
(a) Suppose you are forbidden to move any disk directly between peg 1 andpeg 2; every move must involve peg 0. Describe an algorithm to solve
this version of the puzzle in as few moves as possible. Exactly how many
moves does your algorithm make?
(b) Suppose you are only allowed to move disks from peg 0 to peg 2, frompeg 2 to peg 1, or from peg 1 to peg 0. Equivalently, suppose the pegs
are arranged in a circle and numbered in clockwise order, and you are
only allowed to move disks counterclockwise. Describe an algorithm tosolve this version of the puzzle in as few moves as possible. How many
moves does your algorithm make?

®™

���. R��������

0

1

2

3

4

5

6

7

8

9

Figure �.�8. The �rst several moves in a counterclockwise Towers of Hanoi solution.

®™

(c) Finally, suppose your only restriction is that you may never move a disk
directly from peg 0 to peg 2. Describe an algorithm to solve this versionof the puzzle in as few moves as possible. How many moves does youralgorithm make? [Hint: Matrices! This variant is considerably harderto analyze than the other two.]. Consider the following more complex variant of the Tower of Hanoi puzzle
The puzzle has a row of k pegs, numbered from 1 to k. In a single turn, youare allowed to move the smallest disk on peg i to either peg i 1 or peg i + 1,
for any index i; as usual, you are not allowed to place a bigger disk on asmaller disk. Your mission is to move a stack of n disks from peg 1 to peg k.
(a) Describe a recursive algorithm for the case k = 3. Exactly how many
moves does your algorithm make? (This is exactly the same as problem(a).)(b) Describe a recursive algorithm for the case k = n + 1 that requires atmost O(n3 ) moves. [Hint: Use part (a).]™

™

(c) Describe a recursive algorithm for the case k = n + 1 that requires atmost O(n2 ) moves. [Hint: Don’t use part (a).]p(d) Describe a recursive algorithm for the case k = n that requires at mosta polynomial number of moves. (Which polynomial??)™(e) Describe and analyze a recursive algorithm for arbitrary n and k. How

small must k be (as a function of n) so that the number of moves isbounded by a polynomial in n?

�8

Exercises

Recursion Trees. Use recursion trees to solve each of the following recurrences.
pA(n) = 2A(n/4) + n
B(n) = 2B(n/4) + n C(n) = 2C(n/4) + n2pD(n) = 3D(n/3) + n E(n) = 3E(n/3) + n F (n) = 3F (n/3) + n2pG(n) = 4G(n/2) + n H(n) = 4H(n/2) + n I(n) = 4I(n/2) + n2
. Use recursion trees to solve each of the following recurrences.
(j) J(n) = J(n/2) + J(n/3) + J(n/6) + n(k) K(n) = K(n/2) + 2K(n/3) + 3K(n/4) + n2p(l) L(n) = L(n/15) + L(n/10) + 2L(n/6) + n™

. Use recursion trees to solve each of the following recurrences.
(m) M (n) = 2M (n/2) + O(n log n)(n) N (n) = 2N (n/2) + O(n/ log n)pp(p) P(n) = n P( n) + nppp(q) Q(n) = 2n Q( 2n) + n

Sorting. Suppose you are given a stack of n pancakes of different sizes. You want tosort the pancakes so that smaller pancakes are on top of larger pancakes.
The only operation you can perform is a flip—insert a spatula under the
top k pancakes, for some integer k between 1 and n, and flip them all over.

Figure �.��. Flipping the top four pancakes.

(a) Describe an algorithm to sort an arbitrary stack of n pancakes using
O(n) flips. Exactly how many flips does your algorithm perform in theworst case? [Hint: This problem has nothing to do with the Tower ofHanoi.]The exact worst-case optimal number of flips required to sort n pancakes (either burned or
unburned) is an long-standing open problem; just do the best you can.

���. R��������

(b) For every positive integer n, describe a stack of n pancakes that requires⌦(n) flips to sort.
(c) Now suppose one side of each pancake is burned. Describe an algorithm
to sort an arbitrary stack of n pancakes, so that the burned side of every
pancake is facing down, using O(n) flips. Exactly how many flips does
your algorithm perform in the worst case?
. Recall that the median-of-three heuristic examines the first, last, and middle
element of the array, and uses the median of those three elements as aquicksort pivot. Prove that quicksort with the median-of-three heuristic
requires ⌦(n2 ) time to sort an array of size n in the worst case. Specifically,
for any integer n, describe a permutation of the integers 1 through n,such that in every recursive call to median-of-three-quicksort, the pivot isalways the second smallest element of the array. Designing this permutation
requires intimate knowledge of the P
subroutine.
(a) As a warm-up exercise, assume that the P
subroutine is stable,
meaning it preserves the existing order of all elements smaller than thepivot, and it preserves the existing order of all elements smaller thanthe pivot.
™

(b) Assume that the P
subroutine uses the specific algorithm listed
on page , which is not stable.

. (a) Hey, Moe! Hey, Larry! Prove that the following algorithm actually sorts
its input!
S

S(A[0 .. n 1]) :if n = 2 and A[0] > A[1]swap A[0] $ A[1]else if n > 2
m = d2n/3e
SS(A[0 .. m 1])
S
S(A[n m .. n 1])
S
S(A[0 .. m 1])(b) Would S
S
still sort correctly if we replaced m = d2n/3e withm = b2n/3c? Justify your answer.
(c) State a recurrence (including the base case(s)) for the number ofcomparisons executed by S
S.

(d) Solve the recurrence, and prove that your solution is correct. [Hint:
Ignore the ceiling.](e) Prove that the number of swaps executed by S

S

is at mostn2 .

. The following cruel and unusual sorting algorithm was proposed by Gary
Miller:��

Exercises

CU(A[1 .. n]):
if n > 1
C(A[1 .. n/2])
C(A[n/2 + 1 .. n])
U(A[1 .. n])(A[1 .. n]):
if n = 2
if A[1] > A[2]swap A[1] $ A[2]
else
for i
1 to n/4
swap A[i + n/4] $ A[i + n/2]
U
(A[1 .. n/2])
U(A[n/2 + 1 .. n])
U(A[n/4 + 1 .. 3n/4])hhthe only comparison!ii
hhswap �nd and �rd quartersii
hhrecurse on left half ii
hhrecurse on right half ii
hhrecurse on middle half ii

The comparisons performed by this algorithm do not depend at all on
the values in the input array; such a sorting algorithm is called oblivious.
Assume for this problem that the input size n is always a power of 2.
(a) Prove by induction that C
correctly sorts any input array. [Hint:
Consider an array that contains n/4 1s, n/4 2s, n/4 3s, and n/4 4s. Whyis this special case enough?]would not correctly sort if we removed the for-loop(b) Prove that Cfrom U.
(c) Prove that C
lines of U.

would not correctly sort if we swapped the last two(d) What is the running time of U(e) What is the running time of C

? Justify your answer.
? Justify your answer.

. An inversion in an array A[1 .. n] is a pair of indices (i, j) such that i < j andA[i] > A[ j]. The number of inversions in an n-element array is between 0n(if the array is sorted) and 2 (if the array is sorted backward). Describe
and analyze an algorithm to count the number of inversions in an n-element
array in O(n log n) time. [Hint: Modify mergesort.]. (a) Suppose you are given two sets of n points, one set {p1 , p2 , . . . , pn } on theline y = 0 and the other set {q1 , q2 , . . . , qn } on the line y = 1. Create a setof n line segments by connect each point pi to the corresponding point qi .
Describe and analyze a divide-and-conquer algorithm to determine how
many pairs of these line segments intersect, in O(n log n) time. [Hint:
See the previous problem.](b) Now suppose you are given two sets {p1 , p2 , . . . , pn } and {q1 , q2 , . . . , qn }of n points on the unit circle. Connect each point pi to the corresponding���. R��������

point qi . Describe and analyze a divide-and-conquer algorithm todetermine how many pairs of these line segments intersect in O(n log2 n)time. [Hint: Use your solution to part (a).]™

(c) Describe an algorithm for part (b) that runs in O(n log n) time. [Hint:
Use your solution from part (b)!]
p4
q5

q1 q2

q4

q7

q3

p3

q7

q6

q6

p1

q4
p2
p1

p7

p4

p3

p6

p2

p5

p5
q1
p6

p7 q3 q5

q2

Figure �.��. Eleven intersecting pairs of segments with endpoints on parallel lines, and ten intersecting
pairs of segments with endpoints on a circle.

. (a) Describe an algorithm that sorts an input array A[1a⇥ .. n] by callingp ⇤subroutine S
S(k), which sorts the subarray A k + 1 .. k + n inpplace, given an arbitrary integer k between 0 and nn as input. (Topsimplify the problem, assume that n is an integer.) Your algorithm isonly allowed to inspect or modify the input array by calling S
S;
in particular, your algorithm must not directly compare, move, or copy
array elements. How many times does your algorithm call S
S
in
the worst case?
®

(b) Prove that your algorithm from part (a) is optimal up to constant factors.
In other words, if f (n) is the number of times your algorithm calls
S
S, prove that no algorithm can sort using o( f (n)) calls toSS.
(c) Now suppose S
S
is implemented recursively, by calling yoursorting algorithm from part (a). For example, at the second level ofrecursion, the algorithm is sorting arrays roughly of size n1/4 . Whatis the worst-case running time of the resulting sorting algorithm? (Toksimplify the analysis, assume that the array size n has the form 22 , sothat repeated square roots are always integers.)

Selection. Suppose we are given a set S of n items, each with a value and a weight. For
any element x 2 S, we define two subsets
��Exercises• S<x is the set of elements of S whose value is less than the value of x.
• S>x is the set of elements of S whose value is more than the value of x.
For any subset R ✓ S, let w(R) denote the sum of the weights of elements in R.
The weighted median of R is any element x such that w(S<x )  w(S)/2and w(S>x )  w(S)/2.
Describe and analyze an algorithm to compute the weighted medianof a given weighted set in O(n) time. Your input consists of two unsorted
arrays S[1 .. n] and W [1 .. n], where for each index i, the ith element hasvalue S[i] and weight W [i]. You may assume that all values are distinct and
all weights are positive.

. (a) Describe an algorithm to determine in O(n) time whether an arbitraryarray A[1 .. n] contains more than n/4 copies of any value.
(b) Describe and analyze an algorithm to determine, given an arbitraryarray A[1 .. n] and an integer k, whether A contains more than k copies
of any value. Express the running time of your algorithm as a functionof both n and k.
Do not use hashing, or radix sort, or any other method that depends
on the precise input values, as opposed to their order.
. Describe an algorithm to compute the median of an array A[1 .. 5] of distinct
numbers using at most 6 comparisons. Instead of writing pseudocode,
describe your algorithm using a decision tree: A binary tree where eachinternal node contains a comparison of the form “A[i] ø A[ j]?” and eachleaf contains an index into the array.
A[1]:A[2]<A[1]:A[3]A[1]:A[3]<<A[2]:A[3]

< >
A[2]

>

A[3]

>
A[1]

A[1]

>
A[2]:A[3]

< >
A[3]

A[2]

Figure �.��. Finding the median of a �-element array using at most � comparisons. Consider the generalization of the Blum-Floyd-Pratt-Rivest-Tarjan M S
algorithm shown in Figure . , which partitions the input array intodn/be blocks of size b, instead of dn/5e blocks of size 5, but is otherwise
identical.
���. R��������

M(A[1 .. n], k):bS

if n  b2
use brute forceelse
m dn/befor i
1 to mM [i] M
mom b
M bS
r

P

O B(A[b(i 1) + 1 .. bi])
(M [1 .. m], bm/2c)(A[1 .. n], mom b )if k < rreturn M b S
else if k > r
return M b S
else
return mom b(A[1 .. r1], k)(A[r + 1 .. n], kr)

Figure �.��. A parametrized family of selection algorithms; see problem ��.

(a) State a recurrence for the running time of M b S, assuming that b
is a constant (so the subroutine M
O B runs in O(1) time). In
particular, how do the sizes of the recursive subproblems depend on theconstant b? Consider even b and odd b separately.
(b) What is the worst-case running time of M
trick question.]

1S? [Hint: This is a(c) What is the worst-case running time of M
unfair question!]

2S? [Hint: This is an®™

™

(d) What is the worst-case running time of M 3 S? Finding an upperbound on the running time is straightforward; the hard part is showingthat this analysis is actually tight. [Hint: See problem .]™

(e) What is the worst-case running time of M 4 S? Again, the hardpart is showing that the analysis cannot be improved.
(f) For any constants b 5, the algorithm M b S
runs in O(n) time,
but different values of b lead to different constant factors. Let M (b)denote the minimum number of comparisons required to find the medianof b numbers. The exact value of M (b) is known only for b  13:b
M (b)

1 2 3 4 5 6 7
8
9 10 11 12 13
0 1 3 4 6 8 10 12 14 16 18 20 23

The median of four elements is either the second smallest or the second largest. In,
Ke Chen and Adrian Dumitrescu proved that if we modify M 4 S
to find second-smallest
elements when k < n/2 and second-largest elements when k > n/2, the resulting algorithm runsin O(n) time! See their paper “Select with Groups of 3 or 4 Takes Linear Time” (WADS,
arXiv:.
) for details.

��Exercises

For each b between 5 and 13, find an upper bound on the running timeof M b Sof the form T (n)  ↵ b n for some explicit constant ↵ b .
(For example, on page
we showed that ↵5  16.)(g) Which value of b yields the smallest constant ↵ b ? [Hint: This is a trickquestion!]. Prove that the variant of the Blum-Floyd-Pratt-Rivest-Tarjan S
algorithm shown in Figure . , which uses an extra layer of small medians tochoose the main pivot, runs in O(n) time.
M

S(A[1 .. n], k):
if n  81
use brute forceelse
m dn/3efor i
1 to mM [i] M
O (A[3i 2 .. 3i])
mm dm/3efor j
1 to mmMom[ j] M
O (M [3 j 2 .. 3 j])
momom M
S
(Mom[1 .. mm], bmm/2c)rP(A[1 .. n], momom)
if k < rreturn M
S(A[1 .. r 1], k)else if k > r
return M
S(A[r + 1 .. n], k r)
else
return momom
Figure �.��. Selection by median of moms; see problem ��).

. (a) Suppose we are given two sorted arrays A[1 .. n] and B[1 .. n]. Describe
an algorithm to find the median element in the union of A and B in⇥(log n) time. You can assume that the arrays contain no duplicate
elements.
(b) Suppose we are given two sorted arrays A[1 .. m] and B[1 .. n] and an
integer k. Describe an algorithm to find the kth smallest element in
A [ B in ⇥(log(m + n)) time. For example, if k = 1, your algorithm
should return the smallest element of A [ B.) [Hint: Use your solution
to part (a).]™

(c) Now suppose we are given three sorted arrays A[1 .. n], B[1 .. n], andC[1 .. n], and an integer k. Describe an algorithm to find the kth smallest
element in A [ B [ C in O(log n) time.
���. R��������

(d) Finally, suppose we are given a two dimensional array A[1 .. m, 1 .. n] inwhich every row A[i, ·] is sorted, and an integer k. Describe an algorithm
to find the kth smallest element in A as quickly as possible. How does
the running time of your algorithm depend on m? [Hint: Solve problem
first.]

Arithmetic. In, archaeologists discovered Sumerians clay tablets, carved around, that list the squares of integers up to 59. This discovery led somescholars to conjecture that ancient Sumerians performed multiplication by
reduction to squaring, using an identity like x · y = (x 2 + y 2 (x y)2 )/2.
Unfortunately, those same scholars are silent on how the Sumerians supposedly squared larger numbers. Four thousand years later, we can finallyrescue these Sumerian mathematicians from their lives of drudgery throughthe power of recursion!

(a) Describe a variant of Karatsuba’s algorithm that squares any n-digit
number in O(nlg 3 ) time, by reducing to squaring three dn/2e-digit
numbers. (Karatsuba actually did this in.)(b) Describe a recursive algorithm that squares any n-digit number inO(nlog3 6 ) time, by reducing to squaring six dn/3e-digit numbers.

™

(c) Describe a recursive algorithm that squares any n-digit number inO(nlog3 5 ) time, by reducing to squaring only five (n/3 + O(1))-digit
numbers. [Hint: What is (a + b + c)2 + (a b + c)2 ?]. (a) Describe and analyze a variant of Karatsuba’s algorithm that multiplies any m-digit number and any n-digit number, for any n m, inO(nmlg 3 1 ) time.
(b) Describe an algorithm to compute the decimal representation of 2n inO(nlg 3 ) time, using the algorithm from part (a) as a subroutine. (Thestandard algorithm that computes one digit at a time requires ⇥(n2 )time.)(c) Describe a divide-and-conquer algorithm to compute the decimal representation of an arbitrary n-bit binary number in O(nlg 3 ) time. [Hint:
Watch out for an extra log factor in the running time.]™

�6(d) Suppose we can multiply two n-digit numbers in O(M (n)) time. Describe
an algorithm to compute the decimal representation of an arbitrary n-bit
binary number in O(M (n) log n) time. [Hint: The analysis is the hardpart; use a domain transformation.]

Exercises. Consider the following classical recursive algorithm for computing thefactorial n! of a non-negative integer n:
F(n):
if n = 0
return 1
else
return n · F(n1)(a) How many multiplications does this algorithm perform?
(b) How many bits are required to write n! in binary? Express your answer
in the form ⇥( f (n)), for some familiar function f (n). [Hint: (n/2)n/2 <n! < nn .](c) Your answer to (b) should convince you that the number of multiplications
is not a good estimate of the actual running time of F
. We
can multiply any k-digit number and any l-digit number in O(k · l) timeusing either the lattice algorithm or duplation and mediation. What is
the running time of F
if we use this multiplication algorithm asa subroutine?
(d) The following recursive algorithm also computes the factorial function,
but using a different grouping of the multiplications:F(n, m):
if m = 0
return 1
else if m = 1
return n
else
return F

hhCompute n!/(n(n, bm/2c) · F

m)!ii

(n

bm/2c, dm/2e)What is the running time of F(n, n) if we use grade-school multiplication? [Hint: As usual, ignore the floors and ceilings.](e) Describe and analyze a variant of Karatsuba’s algorithm that multiplies
any k-digit number and any l-digit number, for any kl, in O(k ·lg 3 10.585
l) = O(k · l) time.
(f) What are the running times of F(n) and F
use the modified Karatsuba multiplication from part (e)?

™

(n, n) if we. The greatest common divisor of two positive integer x and y, denoted
gcd(x , y), is the largest integer d such that both x/d and y/d are integers.
Euclid’s Elements, written around, describes the following recursivealgorithm to compute gcd(x, y):Euclid’s algorithm is sometimes incorrectly described as the oldest recursive algorithm,
or even the oldest nontrivial algorithm, even though the Egyptian duplation and mediation
algorithm—which is both nontrivial and recursive—predates Euclid by at least
years.

���. R��������

E

GCD(x, y):
if x = yreturn x
else if x > yreturn E
else
return E

GCD(x

y, y)

GCD(x, yx)(a) Prove that E
GCD correctly computes gcd(x, y). Specifically:i. Prove that E
GCD(x, y) divides both x and y.
ii. Prove that every divisor of x and y is a divisor of E(b) What is the worst-case running time of E
of x and y? (Assume that computing x
time.)GCD(x, y).

GCD(x, y), as a function
y requires O(log x + log y)(c) Prove that the following algorithm also computes gcd(x, y):F

E
GCD(x, y):
if y = 0
return x
else if x > yreturn F E
else
return F E

GCD( y, x mod y)
GCD(x, y mod x)(d) What is the worst-case running time of F E
GCD(x, y), as afunction of x and y? (Assume that computing x mod y takes O(log x ·log y) time.)(e) Prove that the following algorithm also computes gcd(x, y):B

GCD(x, y):
if x = yreturn x
else if x and y are both evenreturn 2 · B
GCD(x/2, y/2)
else if x is evenreturn B
GCD(x/2, y)else if y is evenreturn B
GCD(x, y/2)
else if x > yreturn B
GCD((x y)/2, y)else
return B
GCD(x, ( y x)/2)

Euclid did not do this. Proposition in Elements Book VII states that if E
GCD(x, y) = 1,
then x and y are relatively prime (that is, gcd(x, y) = 1), but the proof only considers the special
case x mod ( y mod (x mod y)) = 1. Proposition states that if x and y are not relatively prime,then E
GCD(x, y) = gcd(x, y), but the proof only considers the special cases gcd(x, y) = y
and gcd(x, y) = y mod (x mod y). Finally, these two Propositions do not make a complete proof
that EGCD is correct. Don’t be like Euclid.

�8

Exercises(f) What is the worst-case running time of B
GCD(x, y), as a functionof x and y? (Assume that computing x y takes O(log x + log y) time,and computing z/2 requires O(log z) time.)

Arrays. Suppose you are given a 2n ⇥ 2n checkerboard with one (arbitrarily chosen)square removed. Describe and analyze an algorithm to compute a tiling of
the board by without gaps or overlaps by L-shaped tiles, each composed ofsquares. Your input is the integer n and two n-bit integers representing therow and column of the missing square. The output is a list of the positions
and orientations of (4n 1)/3 tiles. Your algorithm should run in O(4n )time. [Hint: First prove that such a tiling always exists.]. You are a visitor at a political convention (or perhaps a faculty meeting)with n delegates; each delegate is a member of exactly one political party.
It is impossible to tell which political party any delegate belongs to; inparticular, you will be summarily ejected from the convention if you ask.
However, you can determine whether any pair of delegates belong to thesame party by introducing them to each other. Members of the same politicalparty always greet each other with smiles and friendly handshakes; membersof different parties always greet each other with angry stares and insults.
(a) Suppose more than half of the delegates belong to the same politicalparty. Describe an efficient algorithm that identifies all members of thismajority party.
(b) Now suppose there are more than two parties, but one party has aplurality: more people belong to that party than to any other party.
Present a practical procedure to precisely pick the people from theplurality political party as parsimoniously as possible, presuming theplurality party is composed of at least p people. Pretty please.
. Smullyan Island has three types of inhabitants: knights always speak thetruth; knaves always lie; and normals sometimes speak the truth andsometimes don’t. Everyone on the island knows everyone else’s name andtype (knight, knave, or normal). You want to learn the type of every
inhabitant.
You can ask any inhabitant to tell you the type of any other inhabitant.
Specifically, if you ask “Hey X , what is Y ’s type?” then X will respond as
follows:
Real-world politics is much messier than this simplified model, but this is a theory book!

���. R��������

• If X is a knight, then X will respond with Y ’s correct type.
• If X is a knave, then X could respond with either of the types that Y isnot.
• If X is a normal, then X could respond with any of the three types.
The inhabitants will ignore any questions not of this precise form; inparticular, you may not ask an inhabitant about their own type. Asking thesame inhabitant the same question multiple times always yields the sameanswer, so there’s no point in asking any question more than once.
(a) Suppose you know that a strict majority of inhabitants are knights.
Describe an efficient algorithm to identify the type of every inhabitant.
(b) Prove that if at most half the inhabitants are knights, it is impossible todetermine the type of every inhabitant.
. Most graphics hardware includes support for a low-level operation called blit,
or block transfer, which quickly copies a rectangular chunk of a pixel map(a two-dimensional array of pixel values) from one location to another. Thisis a two-dimensional version of the standard C library function memcpy().
Suppose we want to rotate an n ⇥ n pixel map 90 clockwise. One way to
do this, at least when n is a power of two, is to split the pixel map into fourn/2 ⇥ n/2 blocks, move each block to its proper position using a sequence offive blits, and then recursively rotate each block. (Why five? For the same
reason the Tower of Hanoi puzzle needs a third peg.) Alternately, we could
first recursively rotate the blocks and then blit them into place.
A B
C D

recurse5 blits

C D

recurse

A B

C A
D B

B D
A C

5 blits

A B
C D

A B
C D

Figure �.��. Two algorithms for rotating a pixel map.

(a) Prove that both versions of the algorithm are correct when n is a powerof 2.
(b) Exactly how many blits does the algorithm perform when n is a powerof 2?
(c) Describe how to modify the algorithm so that it works for arbitrary n,
not just powers of 2. How many blits does your modified algorithm
perform?
(d) What is your algorithm’s running time if a k ⇥ k blit takes O(k2 ) time?
(e) What if a k ⇥ k blit takes only O(k) time?

. An array A[0 .. n 1] of n distinct numbers is bitonic if there are unique
indices i and j such that A[(i 1) mod n] < A[i] > A[(i + 1) mod n] and6�

Exercises

Figure �.��. The �rst rotation algorithm (blit then recurse) in action. (See Image Credits at the end of
the book.)A[( j 1) mod n] > A[ j] < A[( j + 1) mod n]. In other words, a bitonic
sequence either consists of an increasing sequence followed by a decreasing
sequence, or can be circularly shifted to become so. For example,
4

6

9

8

7

5

1

2

3

is bitonic, but

3

6

9

8

7

5

1

2

4

is not bitonic.

Describe and analyze an algorithm to find the smallest element in an nelement bitonic array in O(log n) time. You may assume that the numbersin the input array are distinct.
. Suppose we are given an array A[1 .. n] of n distinct integers, which could bepositive, negative, or zero, sorted in increasing order so that A[1] < A[2] <· · · < A[n].

(a) Describe a fast algorithm that either computes an index i such that
A[i] = i or correctly reports that no such index exists.

(b) Suppose we know in advance that A[1] > 0. Describe an even faster
algorithm that either computes an index i such that A[i] = i or correctly
reports that no such index exists. [Hint: This is really easy.]. Suppose we are given an array A[1 .. n] with the special property that
A[1] A[2] and A[n 1]  A[n]. We say that an element A[x] is a local
minimum if it is less than or equal to both its neighbors, or more formally,
if A[x 1] A[x] and A[x]  A[x + 1]. For example, there are six local
minima in the following array:
9

7

Œ

7

2

1

Œ

3

7

5

4

Œ

7

3

Œ

3

Œ

4

8

6

Œ

9
6�

�. R��������

We can obviously find a local minimum in O(n) time by scanning throughthe array. Describe and analyze an algorithm that finds a local minimum inO(log n) time. [Hint: With the given boundary conditions, the array musthave at least one local minimum. Why?]. Suppose you are given a sorted array of n distinct numbers that has been
rotated k steps, for some unknown integer k between 1 and n 1. That is,
you are given an array A[1 .. n] such that some prefix A[1 .. k] is sorted inincreasing order, the corresponding suffix A[k + 1 .. n] is sorted in increasingorder, and A[n] < A[1].
For example, you might be given the following
k = 10):9 13 16 18 19 23 28 31 37 42-element array (where

1 3 4 5 7 8(a) Describe and analyze an algorithm to compute the unknown integer k.
(b) Describe and analyze an algorithm to determine if the given array
contains a given number x.
. At the end of the second act of the action blockbuster Fast and ImpossibleXIIIæ: The Last Guardians of Expendable Justice Reloaded,the villainous
Dr. Metaphor hypnotizes the entire Hero League/Force/Squad, arranges
them in a long line at the edge of a cliff, and instructs each hero to shootthe closest taller heroes to their left and right, at a prearranged signal.
Suppose we are given the heights of all n heroes, in order from left
to right, in an array Ht[1 .. n]. (To avoid salary arguments, the producers
insisted that no two heroes have the same height.) Then we can computethe Left and Right targets of each hero in O(n2 ) time using the following
brute-force algorithm.
W

T
for j

W
1 to n(Ht[1 .. n]):hhFind the left target L[ j] for hero jii
L[ j] Nfor i
1 to j 1
if Ht[i] > Ht[ j]L[ j]ihhFind the right target R[ j] for hero jii
R[ j] Nfor kn down to j + 1
if Ht[k] > Ht[ j]R[ j]kreturn L[1 .. n], R[1 .. n]
6�

Exercises(a) Describe a divide-and-conquer algorithm that computes the output of
W T
W
in O(n log n) time.
(b) Prove that at least bn/2c of the n heroes are targets. That is, prove thatthe output arrays R[0 .. n 1] and L[0 .. n 1] contain at least bn/2c
distinct values (other than N).
(c) Alas, Dr. Metaphor’s diabolical plan is successful. At the prearranged
signal, all the heroes simultaneously shoot their targets, and all targets
fall over the cliff, apparently dead. Metaphor repeats his dastardly
experiment over and over; after each massacre, he forces the remaining
heroes to choose new targets, following the same algorithm, and thenshoot their targets at the next signal. Eventually, only the shortest
member of the Hero Crew/Alliance/Posse is left alive.
Describe and analyze an algorithm to compute the number of rounds
before Dr. Metaphor’s deadly process finally ends. For full credit, youralgorithm should run in O(n) time.
. You are a contestant on the hit game show “Beat Your Neighbors!” You arepresented with an m ⇥ n grid of boxes, each containing a unique number. It
costs $
to open a box. Your goal is to find a box whose number is larger
than its neighbors in the grid (above, below, left, and right). If you spend
less money than any of your opponents, you win a week-long trip for two to
Las Vegas and a year’s supply of Rice-A-Roni , to which you are hopelessly
addicted.
(a) Suppose m = 1. Describe an algorithm that finds a number that is bigger
than either of its neighbors. How many boxes does your algorithm open
in the worst case?
™

(b) Suppose m = n. Describe an algorithm that finds a number that is bigger
than any of its neighbors. How many boxes does your algorithm open in
the worst case?
(c) Prove that your solution to part (b) is optimal up to a constant factor.

®™

. (a) Let n = 2` 1 for some positive integer `. Suppose someone claims tohold an unsorted array A[1 .. n] of distinct `-bit strings; thus, exactly one`-bit string does not appear in A. Suppose further that the only way wecan access A is by calling the function F
B (i, j), which returns thejth bit of the string A[i] in O(1) time. Describe an algorithm to find themissing string in A using only O(n) calls to FB .
In the thrilling final act, Retcon the Squirrel, the last surviving member of the Hero
Team/Group/Society, saves everyone by traveling back in time and retroactively replacing theother n 1 heroes with lifelike balloon sculptures. So, yeah, basically it’s Avengers: Endgame.

6��. R��������™

(b) Now suppose n = 2` k for some positive integers k and `, and again weare given an array A[1 .. n] of distinct `-bit strings. Describe an algorithm
to find the k strings that are missing from A using only O(n log k) calls
to F
B .

Trees
. For this problem, a subtree of a binary tree means any connected subgraph.
A binary tree is complete if every internal node has two children, and every
leaf has exactly the same depth. Describe and analyze a recursive algorithm
to compute the largest complete subtree of a given binary tree. Your algorithm
should return both the root and the depth of this subtree. See Figure .
for an example.

Figure �.�6. The largest complete subtree of this binary tree has depth �.

. Let T be a binary tree with n vertices. Deleting any vertex v splits T into at
most three subtrees, containing the left child of v (if any), the right childof v (if any), and the parent of v (if any). We call v a central vertex if
each of these smaller trees has at most n/2 vertices. See Figure . for an
example.
Describe and analyze an algorithm to find a central vertex in an arbitrary
given binary tree. [Hint: First prove that every tree has a central vertex.]
34

14

7

12

Figure �.��. Deleting a central vertex in a ��-node binary tree, leaving subtrees with ��, �, and �� nodes.

6�

Exercises. (a) Professor George O’Jungle has a -node binary tree, in which every
node is labeled with a unique letter of the Roman alphabet or thecharacter &. Preorder and postorder traversals of the tree visit the nodes
in the following order:• Preorder: I Q J H L E M V O T S B R G Y Z K C A & F P N U D W X• Postorder: H E M L J V Q S G Y R Z B T C P U D N F W & X A K O I
Draw George’s binary tree.
(b) Recall that a binary tree is full if every non-leaf node has exactly twochildren.
i. Describe and analyze a recursive algorithm to reconstruct an arbitrary
full binary tree, given its preorder and postorder node sequences as
input.
ii. Prove that there is no algorithm to reconstruct an arbitrary binary
tree from its preorder and postorder node sequences.
(c) Describe and analyze a recursive algorithm to reconstruct an arbitrary
binary tree, given its preorder and inorder node sequences as input.
(d) Describe and analyze a recursive algorithm to reconstruct an arbitrary
binary search tree, given only its preorder node sequence.
™

(e) Describe and analyze a recursive algorithm to reconstruct an arbitrary
binary search tree, given only its preorder node sequence, in O(n) time.
In parts (b)–(e), assume that all keys are distinct and that the input isconsistent with at least one binary tree.

. Suppose we have n points scattered inside a two-dimensional box. A kdtree recursively subdivides the points as follows. If the box contains nopoints in its interior, we are done. Otherwise, we split the box into two
smaller boxes with a vertical line, through a median point inside the box(not on its boundary), partitioning the points as evenly as possible. Then
we recursively build a kd-tree for the points in each of the two smaller
boxes, after rotating themdegrees. Thus, we alternate between splitting
vertically and splitting horizontally at each level of recursion. The final
empty boxes are called cells.
The term “kd-tree” (pronounced “kay dee tree”) was originally an abbreviation for “kdimensional tree”, but modern usage ignores this etymology, in part because nobody in theirright mind would ever use the letter k to denote dimension instead of the obviously superior d.
Etymological consistency would require calling the data structure in this problem a “2d-tree”(or perhaps a “2-d tree”), but the standard nomenclature is now “two-dimensional kd-tree”.
See also: B-tree (maybe), alpha shape, beta skeleton, epsilon net, Potomac River, Mississippi
River, Lake Michigan, Lake Tahoe, Manhattan Island, La Brea Tar Pits, Sahara Desert, Mount
Kilimanjaro, South Vietnam, East Timor, the Milky Way Galaxy, the City of Townsville, andself-driving automobiles.

6��. R��������

Figure �.�8. A kd-tree for �� points. The dashed line crosses the four shaded cells.

(a) How many cells are there, as a function of n? Prove your answer iscorrect.
(b) In the worst case, exactly how many cells can a horizontal line cross, asa function of n? Prove your answer is correct. Assume that n = 2k 1
for some integer k. [Hint: There is more than one function f such thatf (16) = 4.](c) Suppose we are given n points stored in a kd-tree. Describe and analyze
an algorithm that counts the number of points above a horizontal line
(such as the dashed line in the figure) as quickly as possible. [Hint: Usepart (b).](d) Describe an analyze an efficient algorithm that counts, given a kd-tree
containing n points, the number of points that lie inside a rectangle R
with horizontal and vertical sides. [Hint: Use part (c).]™

. Bob Ratenbur, a new student in CS, is trying to write code to perform
preorder, inorder, and postorder traversals of binary trees. Bob sort-ofunderstands the basic idea behind the traversal algorithms, but wheneverhe actually tries to implement them, he keeps mixing up the recursive calls.
Five minutes before the deadline, Bob frantically submits code with thefollowing structure:
P

O
(v):
if v = Nreturnelse
print label(v)O(left(v))
O(right(v))

I O
(v):
if v = Nreturnelse
O(left(v))
print label(v)O(right(v))

P

O
(v):
if v = Nreturnelse
O(left(v))
O(right(v))
print label(v)Eachin this pseudocode hides one of the prefixes P , I , or P.
Moreover, each of the following function calls appears exactly once in Bob’s
submitted code:66

Exercises

P O
I O
P
O

P O
I O
P
O

(left(v))(left(v))(left(v))(right(v))(right(v))(right(v))

Thus, there are precisely
possibilities for Bob’s code. Unfortunately, Bob
accidentally deleted his source code after submitting the executable, soneither you nor he knows which functions were called where.
Now suppose you are given the output of Bob’s traversal algorithms,
executed on some unknown binary tree T . Bob’s output has been helpfullyparsed into three arrays Pre[1 .. n], In[1 .. n], and Post[1 .. n]. You may
assume that these traversal sequences are consistent with exactly one binary
tree T ; in particular, the vertex labels of the unknown tree T are distinct,
and every internal node in T has exactly two children.
(a) Describe an algorithm to reconstruct the unknown tree T from the given
traversal sequences.
(b) Describe an algorithm that either reconstructs Bob’s code from the given
traversal sequences, or correctly reports that the traversal sequences are
consistent with more than one set of algorithms.
For example, given the input
Pre[1 .. n] = [H A E C B I F G D]
In[1 .. n] = [A H D C E I F B G]
Post[1 .. n] = [A E I B F C D G H]
your first algorithm should return the following tree:
H
A

D
C
E

G
B

I

F

and your second algorithm should reconstruct the following code:
P

™

O
(v):
if v = Nreturnelse
print label(v)P O(left(v))
PO(right(v))

I O
(v):
if v = Nreturnelse
PO(left(v))
print label(v)P O(right(v))

P

O
(v):
if v = Nreturnelse
I O(left(v))
I O(right(v))
print label(v). Let T be a binary tree whose nodes store distinct numerical values. Recall
that T is a binary search tree if and only if either ( ) T is empty, or ( ) T
satisfies the following recursive conditions:6��. R��������

• The left subtree of T is a binary search tree.
• All values in the left subtree are smaller than the value at the root.
• The right subtree of T is a binary search tree.
• All values in the right subtree are larger than the value at the root.
Consider the following pair of operations on binary trees:• Rotate an arbitrary node upward.
y

x
y

x

C
A

A

B

B

C

• Swap the left and right subtrees of an arbitrary node.
x

x

A

B

B

A

In both of these operations, some, all, or none of the subtrees A, B, and C
could be empty.
(a) Describe an algorithm to transform an arbitrary n-node binary treewith distinct node values into a binary search tree, using at most O(n2 )rotations and swaps. Figure . shows a sequence of eight operations
that transforms a five-node binary tree into a binary search tree.
3
1

3
4

5

1

2
2

2

4
5

2

3
1

3
4

5

3

4
5

4

4
1

5

2

5

4
3

1

5

3

2
1

4

2

4

5

2
1

2
3

1

5
3

1

Figure �.��. “Sorting” a binary tree: rotate �, rotate �, swap �, rotate �, rotate �, swap �, rotate �, swap �.

Your algorithm is not allowed to directly modify parent or childpointers, create new nodes, or delete old nodes; the only way to modify
the tree is through rotations and swaps.
On the other hand, you may compute anything you like for free, aslong as that computation does not modify the tree; the running time ofyour algorithm is defined to be the number of rotations and swaps that it
performs.
™

(b) Describe an algorithm to transform an arbitrary n-node binary tree intoa binary search tree, using at most O(n log n) rotations and swaps.

Rotations preserve the inorder sequence of nodes in a binary tree. Partly for this reason,rotations are used to maintain several types of balanced binary search trees, including AVL trees,
red-black trees, splay trees, scapegoat trees, and treaps. See http://algorithms.wtf for lecturenotes on most of these data structures.

68

Exercises(c) Prove that any n-node binary search tree can be transformed into any
other binary search tree with the same node values, using only O(n)rotations (and no swaps).
™(d) Open problem: Either describe an algorithm to transform an arbitrary

n-node binary tree into a binary search tree using only O(n) rotations
and swaps, or prove that no such algorithm is possible. [Hint: I don’t
think it’s possible.]

6�