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. 400CE), translated by Lionel Giles (1910) Our life is frittered away by detail. . . . Simplify, simplify.
— Henry David Thoreau, Walden (1854) 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 (1958)
Do the hard jobs first. The easy jobs will take care of themselves.
1.1 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, the correctness 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 our business; they’re somebody else’s problem. It’s often best to literally think of the black 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
— attributed to Dale Carnegie
1 Recursion
1
1. RECURSION
2
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 the running 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 the operations Insert and ExtractMax. The abstract data type “priority queue” is a black box; the correctness of the apportionment algorithm does not depend on any specific priority queue data structure. Of course, the running time of the apportionment algorithm depends on the running time of the Insert and ExtractMax algorithms, but that’s a separate issue from the correctness of the algorithm. 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 know or 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 to pretend that you don’t.
1.2 Simplify and Delegate
Recursion is a particularly powerful kind of reduction, which can be described loosely as follows:
• If the given instance of the problem can be solved directly, solve it directly. • Otherwise,reduceittooneormoresimplerinstancesofthesameproblem.
If the self-reference is confusing, it may be helpful to imagine that someone else is going to solve the simpler problems, just as you would assume for other types of 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 simplification is 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
1.2. Simplify and Delegate
Out.1 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 the same problem. For example, if the original input is a skreeble with n glurps, the input 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 have negative glurps; that would be silly!—so in that case we must grindlebloff the skreeble 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 identity.
0 if x = 0 x·y= ⌊x/2⌋·(y+y) ifxiseven
⌊x/2⌋·(y+y)+y ifxisodd The same identity can be expressed algorithmically as follows:
Multiply(x, y): if x = 0
return 0 else
x′ ←⌊x/2⌋ y′ ← y + y
prod ← Multiply(x′, y′) if x is odd
prod ← prod + y return prod
〈〈Recurse!〉〉
A lazy Egyptian scribe could execute this algorithm by computing x′ and y’, asking a more junior scribe to multiply x′ and y′, and then possibly adding y to the junior scribe’s response. The junior scribe’s problem is simpler because x′ < x, and repeatedly decreasing a positive integer eventually leads to 0. How the junior scribe actually computes x′ · y′ is none of the senior scribe’s business (and it’s none of your business, either).
1When 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 unfinished when he goes to bed, only to discover upon waking that elves (“Wichtelmänner”) have finished everything overnight. Someone more entheogenically experienced than I might recognize these Rekursionswichtelmänner as Terence McKenna’s “self-transforming machine elves”.
3
1. RECURSION
1.3 Tower of Hanoi
The Tower of Hanoi puzzle was first published—as an actual physical puzzle!—by the French teacher and recreational mathematician Éduoard Lucas in 1883,2 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:3
In the great temple at Benares4 . . . beneath the dome which marks the centre of the world, rests a brass plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass 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 fixed and immutable laws of Bramah, which require that the priest on duty must not move more than 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 thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.
Figure 1.1. The Tower of Hanoi puzzle
Of course, as good computer scientists, our first instinct on reading this story 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 of
2Lucas later claimed to have invented the puzzle in 1876.
3This English translation is taken from W. W. Rouse Ball’s 1892 book Mathematical Recreations and Essays.
4The “great temple at Benares” is almost certainly the Kashi Vishvanath Temple in Varanasi, Uttar Pradesh, India, located approximately 2400km west-north-west of Hà Nô. i, Viê. t Nam, where the fictional N. Claus supposedly resided. Coincidentally, the French Army invaded Hanoi in 1883, the same year Lucas released his puzzle, ultimately leading to its establishment as the capital of French Indochina.
4
“needles”. How can we move a tower of n disks from one peg to another, using a third peg as an occasional placeholder, without ever placing a disk on top of 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 disks to the third peg. And then after we move the largest disk, we have to move those n − 1 disks back on top of it.
recursion
Figure 1.2. 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 number of 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, are quite adept at moving zero disks from one peg to another in no time at all, by doing nothing.
Figure 1.3. The vacuous base case for the Tower of Hanoi algorithm. There is no spoon.
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
1.3. Tower of Hanoi
recursion
5
1. RECURSION
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 such a reduction is impossible. Our recursive Tower of Hanoi algorithm is trivially correct 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 recursive algorithm correctly moves the top n − 1 disks) so our algorithm is correct.
The recursive Hanoi algorithm is expressed in pseudocode in Figure 1.4. The algorithm moves a stack of n disks from a source peg (src) to a destination peg (dst) using a third temporary peg (tmp) as a placeholder. Notice that the algorithm correctly does nothing at all when n = 0.
Figure 1.4. 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 this guess is correct. In particular, moving a tower of 64 disks requires 264 − 1 = 18,446,744,073,709,551,615 individual moves. Thus, even at the impressive rate of one move per second, the monks at Benares will be at work for approximately 585 billion years (“plus de cinq millards de siècles”) before tower, temple, and Brahmins alike will crumble into dust, and with a thunderclap the world will vanish.
1.4 Mergesort
Mergesort is one of the earliest sorting algorithms designed for general-purpose stored-program computers. The algorithm was developed by John von Neumann in 1945, and described in detail in a publication with Herman Goldstine in 1947, as one of the first non-numerical programs for the EDVAC.5
1. Divide the input array into two subarrays of roughly equal size.
5Goldstine 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 Neumann argued (successfully!) that because the EDVAC could sort faster IBM’s dedicated sorters, “without human intervention or need for additional equipment”, the EDVAC was an “all purpose” machine, and special-purpose sorting machines were no longer necessary.
Hanoi(n, src, dst, tmp): if n > 0
Hanoi(n − 1, src, tmp, dst) 〈〈Recurse!〉〉 move disk n from src to dst
Hanoi(n − 1, tmp, dst, src) 〈〈Recurse!〉〉
6
2. Recursively mergesort each of the subarrays.
3. Merge the newly-sorted subarrays into a single sorted array.
Figure 1.5. 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 is done in the final merge step. A complete description of the algorithm is given in Figure 1.6; 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.
1.4. Mergesort
Input: S O R T I N G E X A M P L Divide: S O R T I N G E X A M P L RecurseLeft: I N O S R T G E X A M P L RecurseRight: I N O S R T A E G L M P X Merge: A E G I L M N O P R S T X
Merge(A[1 .. n], m): i←1; j←m+1 for k ← 1 to n
if j > n
B[k]←A[i]; i←i+1
else if i > m
B[k]←A[j]; j←j+1
else if A[i] < A[j] B[k]←A[i]; i←i+1
else
B[k]←A[j]; j←j+1
for k ← 1 to n A[k] ← B[k]
MergeSort(A[1 .. n]): if n > 1
m ← ⌊n/2⌋
MergeSort(A[1 .. m]) 〈〈Recurse!〉〉 MergeSort(A[m+1..n]) 〈〈Recurse!〉〉 Merge(A[1 .. n], m)
Figure 1.6. Mergesort
Correctness
To prove that this algorithm is correct, we apply our old friend induction twice, first to the Merge subroutine then to the top-level Mergesort algorithm.
Lemma1.1. MergecorrectlymergesthesubarraysA[1..m]andA[m+1..n], assuming those subarrays are sorted in the input.
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 last n − k − 1 iterations of the main loop correctly merge A[i .. m] and A[ j .. n] into
7
1. RECURSION
8
B[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,thensubarrayA[j..n]isempty,sominA[i..m]∪A[j..n]=A[i]. • Ifi>m,thensubarrayA[i..m]isempty,sominA[i..m]∪A[j..n]=A[j]. • Otherwise,ifA[i]
Choose a pivot element A[p]
r ← Partition(A, p)
QuickSort(A[1 .. r − 1]) 〈〈Recurse!〉〉 QuickSort(A[r+1..n]) 〈〈Recurse!〉〉
Figure 1.8. Quicksort
Correctness
Just like mergesort, proving that QuickSort is correct requires two separate induction proofs: one to prove that Partition correctly partitions the array, and
6Hoare 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.
9
1. RECURSION
10
the other to prove that QuickSort correctly sorts assuming Partition is correct. To prove Partition 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 .. l] is less than A[n], and nothing in the subarray A[l + 1 .. i] is less than A[n]. I’ll leave the remaining straightforward but tedious details as exercises for the reader.
Analysis
The analysis of quicksort is also similar to that of mergesort. Partition clearly runs in O(n) time, because it’s a simple for-loop with constant work per iteration. For QuickSort, we get a recurrence that depends on r, the rank of the chosen pivot element:
T(n) = T(r − 1) + T(n − r) + O(n)
If we could somehow always choose the pivot to be the median element of the array A, we would have r = ⌈n/2⌉, the two subproblems would be as close to the same size as possible, the recurrence would become
T(n) = 2T⌈n/2⌉−1+T⌊n/2⌋+O(n) ≤ 2T(n/2)+O(n),
and we’d have T (n) = O(n log n) by the recursion tree method.
In fact, as we will see later in this chapter, we can actually locate the median 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 to make 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 have
T(n)= max T(r−1)+T(n−r)+O(n). 1≤r≤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(n2).
Another common heuristic is called “median of three”—choose three ele- ments (usually at the beginning, middle, and end of the array), and take the median of those three elements the pivot. Although this heuristic is somewhat more efficient in practice than just choosing one element, especially when 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 becomes T(n) ≤ T(1) + T(n − 2) + O(n), whose solution is still T(n) = O(n2).
Intuitively, the pivot element should “usually” fall somewhere in the middle of the array, say between n/10 and 9n/10. This observation suggests that
the average-case running time should be O(n log n). Although this intuition is actually correct, it’s correct only under 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 you can predict in advance, and it is certainly not uniform!7
Occasionally people consider “best case” running time for some reason. We won’t.
1.6 The Pattern
Both mergesort and quicksort follow a general three-step pattern called divide and conquer:
1. Divide the given instance of the problem into several independent smaller instances.
2. Delegate each smaller instance to the Recursion Fairy.
3. 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 a recurrence, which usually (but unfortunately not always!) can be solved using recursion trees.
1.7 Recursion Trees
So what are these “recursion trees” I keep talking about? Recursion trees are a 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 the sum 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 calls, each on a problem of size n/c. Up to constant factors (which we can
7 On the other hand, if we choose the pivot index p uniformly at random, then Quicksort runs in O(n log n) time with high probability, for every possible input array. The key difference is that the randomness is controlled by our algorithm, not by the all-powerful malicious adversary who gives 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/.
1.6. The Pattern
11
1. RECURSION
hide in the O( ) notation), the running time of this algorithm is governed by the recurrence
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 d contains the value f (n/cd ). (Feel free to assume that n is an integer power of c, so that n/cd is always an integer, although in fact this doesn’t matter.)
In practice, I recommend drawing out the first two or three levels of the tree, as in Figure 1.9.
f(n)
r
f(n)
+
f(n/c) f(n/c) r ⋅ f(n/c) rrrr+
r2 ⋅ f(n/c2) +
+
LLLLLLLLLL
f(n/c) f(n/c)
f(n/c2) f(n/c2)
f(n/c2) f(n/c2)
f(n/c2) f(n/c2) f(n/c2) f(n/c2)
f(n/c2) f(n/c2)
f(n/c2) f(n/c2)
f(n/c2) f(n/c2) f(n/c2) f(n/c2)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
r ⋅ f(n/c )
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
f(n/c L) f(n/c L) f(n/c L)
12
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
f(n/c )
Figure 1.9. 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 the recurrence. Because we’re only looking for asymptotic bounds, the precise base case 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 whatever value of n0 is most convenient for our analysis. For this example, I’ll choose n0 = 1.
Now T(n) is the sum of all values in the recursion tree; we can evaluate this sum by considering the tree level-by-level. For each integer i, the ith level of the tree has exactly ri nodes, each with value f (n/ci). Thus,
L
T(n) = ri f (n/ci) (Σ)
i=0
where L is the depth of the tree. Our base case n0 = 1 immediately implies L = logc n, because n/cL = n0 = 1. It follows that the number of leaves in the recursion tree is exactly rL = rlogc n = nlogc r. Thus, the last term in the level-by-level sum (Σ) is nlogc r · f (1) = O(nlogc r ), because f (1) = O(1).
1.7. Recursion Trees
There are three common cases where the level-by-level sum (Σ) is especially easy to evaluate:
• Decreasing: If the sum is a decreasing geometric series—every term is a constant factor 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 sum are equal, we immediately have T(n) = O(f(n)·L)=O(f(n)logn). (TheconstantcvanishesintotheO()notation.)
• Increasing: If the sum is an increasing geometric series—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 hold if the recursion tree were infinite!
For 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).
The recursion tree technique can also be used for algorithms where the recursive subproblems have different sizes. As an 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. (Moreover, since n/2 levels each have value at least n/2, this analysis can be improved by at most a constant factor, which for our purposes means not at all.)
nn
n/4
n/2 n/2 n/4 n/4
n/4
n–1 1 n–2 1
n/8
n/8
n/8
n/8
n/8
n/8
n/8
n/8
n–3 Figure 1.10. The recursion trees for mergesort and quicksort
1
13
1. RECURSION
nIgnoring 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 421 or 177? The actual mergesort 28
recurrence is somewhat messier:
T (n) = T ⌈n/2⌉ + T ⌊n/2⌋ + 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 for removing floors and ceilings, called a domain transformation.
• First, we overestimate T(n), once by pretending that the two subproblem sizes are equal, and again to eliminate the ceiling:8
T(n) ≤ 2T⌈n/2⌉+n ≤ 2T(n/2+1)+n.
• Second,wedefineanewfunctionS(n)=T(n+α),choosingtheconstantαso that S(n) satisfies the simpler recurrence of the form 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+α)
≤ 2T(n/2+α/2+1)+n+α = 2S(n/2−α/2+1)+n+α
[definitionofS] [recurrence for T] [definition of S]
Setting α = 2 simplifies this recurrence to S(n) ≤ 2S(n/2) + n + 2, which is exactly what we wanted.
• Finally, the recursion tree method implies S(n) = O(n log n), and therefore T(n) = S(n−2) = O((n−2)log(n−2)) = O(nlogn),
exactly as promised.
Similar domain transformations can be used to remove floors, ceilings, and even lower order terms from any divide and conquer recurrence. But now that we realize 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.
8Formally, we are treating T as a function over the reals, not just over the integers, that satisfies 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.
14
n1.8. Linear-Time Selection
n1.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 early 1970s. Their algorithm actually solves the more general problem of selecting the kth largest element in an n-element array, given the array and the integer k as input, using a variant of an algorithm called quickselect or one-armed quicksort. Quickselect was first described by Tony Hoare in 1961, literally on the same page where he first published quicksort.
The generic quickselect algorithm chooses a pivot element, partitions the array using the same Partition subroutine as QuickSort, and then recursively searches only one of the two subarrays. Crucially, the correctness of this algorithm does not depend on how the pivot is chosen.
QuickSelect(A[1 .. n], k): if n = 1
return A[1] else
Choose a pivot element A[p] r ← Partition(A[1 .. n], p)
if k < r
return QuickSelect(A[1 .. r − 1], k)
else if k > r
return QuickSelect(A[r + 1 .. n], k − r)
else
return A[r]
The worst-case running time of Hoare’s QuickSelect algorithm obeys a recurrence similar to QuickSort. We don’t know the value of r or which of the two subarrays we’ll recursively search, so we’ll just assume the worst.
T(n) ≤ max max{T(r−1),T(n−r)}+O(n) 1≤r≤n
We can simplify the recurrence slightly by letting l denote the length of the recursive subproblem:
T(n) ≤ max T(l)+O(n) 0≤l≤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.)
We could avoid this quadratic worst-case behavior if we could somehow magically choose a good pivot, meaning l ≤ αn for some constant α < 1. In
15
1. RECURSION
this case, the recurrence would simplify to
T (n) ≤ T (αn) + O(n).
This recurrence expands into a descending geometric series, which is dominated by 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 even close 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-Floyd- Pratt-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 ⌈n/5⌉ blocks, each containing exactly 5 elements, except possibly the last. (If the last block isn’t full, just throw in a few ∞s.) We compute the median of each block by brute force, collect those medians into a new array M [1 .. ⌈n/5⌉], and then recursively compute the median of this new array. Finally we use the median of medians (called “mom” in the following pseudocode) as the pivot in one-armed quicksort.
MomSelect(A[1 .. n], k):
if n ≤ 25 〈〈or whatever〉〉
use brute force else
m ← ⌈n/5⌉ for i ← 1 to m
M[i]←MedianOfFive(A[5i−4..5i]) 〈〈Bruteforce!〉〉
mom ← MomSelect(M[1..m],⌊m/2⌋)
r ← Partition(A[1 .. n], mom)
if k < r
return MomSelect(A[1 .. r − 1], k)
else if k > r
return MomSelect(A[r + 1 .. n], k − r)
else
return mom
〈〈Recursion!〉〉
〈〈Recursion!〉〉 〈〈Recursion!〉〉
16
MomSelect uses recursion for two different purposes; once to choose a pivot element (mom), and the second time to search through the entries on one side of that pivot.
Analysis
But why is this fast? The first key insight is that the median of medians is a good pivot. Mom is larger than ⌈n/5⌉/2 − 1 ≈ n/10 block medians, and each
block 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 call searches an array of size at most 7n/10.
We can visualize the algorithm’s behavior by drawing the input array as a 5 × ⌈n/5⌉ grid, which each column represents five consecutive elements. For purposes of illustration, imagine that we sort every column from top down, and then we sort the columns by their middle element. (Let me emphasize that the algorithm 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, each of which is smaller than mom. If the element we’re looking for is larger than mom, 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 is that 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 the algorithm 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 the
n1.8. Linear-Time Selection
17
1. RECURSION
previous level. Thus, the level-by-level sum is a descending geometric series, giving us the solution T (n) = O(n). Hooray! Thanks, Mom!
nn n/5 7n/10 n/3
2n/3
n/25
Figure 1.11. The recursion trees for MomSelect and a similar selection algorithm with blocks of size 3
Sanity Checking
At this point, many students ask about that magic constant 5. Why did we choose that particular block size? The answer is that 5 is the smallest odd block size that gives us a descending geometric series in the running time! (Even block sizes introduce additional complications.) If we had used blocks of 3 elements instead, the running-time recurrence becomes
T(n) ≤ T(n/3) + T(2n/3) + O(n).
In this case, every level of the recursion tree has the same value n. The leaves of the recursion tree are not all at the same level, but for purposes of deriving an upper bound, it suffices to observe that the deepest leaf is at level log3/2 n, so the total work in the tree is at most O(n log3/2 n) = O(n log n). On the other hand, the shallowest leaf has depth log3 n, so the analysis can’t be improved by more than a constant factor. This algorithm 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 9 i 8n
T(n)≤ 5 i≥0 10 = 5 ·10=16n.
7n/50 7n/50 49n/100 n/9
2n/9 2n/9
4n/9
18
1.9. Fast Multiplication
In practice, this algorithm isn’t as horrible as this worst-case analysis pre- dicts—getting a worst-case partition at every level of recursion is incredibly unlikely—but it is slower than sorting for even moderately large arrays.9
1.9 Fast Multiplication
In the previous chapter, we saw two different 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 in half and exploiting the following identity:
(10ma + b)(10mc + d) = 102mac + 10m(bc + ad) + bd
This recurrence immediately suggests the following divide-and-conquer algo- rithm to multiply two n-digit numbers x and y. Each of the four sub-products ac, bc, ad, and bd is computed recursively, but the multiplications in the last line are not recursive, because we can multiply by a power of ten by shifting the digits to the left and filling in the correct number of zeros, all in O(n) time.
Multiply(x, y,n): if n = 1
return x · y else
m ← ⌈n/2⌉
a←⌊x/10m⌋; b←xmod10m c←⌊y/10m⌋; d←ymod10m
e ← Multiply(a, c, m) f ←Multiply(b,d,m) g ← Multiply(b, c, m)
h←Multiply(a,d,m)
return 102me + 10m(g + h) + f
〈〈x=10ma+b〉〉 〈〈y=10mc+d〉〉
Correctness of this algorithm follows easily by induction. The running time for this algorithm follows the recurrence
T (n) = 4T (⌈n/2⌉) + O(n).
The recursion tree method transforms this recurrence into an increasing geo- metric 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.
9In 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 http://algorithms.wtf for more details.
19
1. RECURSION
n
n/2 n/2
n/2 n/2
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
Figure 1.12. The recursion tree for naïve divide-and-conquer multiplication
In the mid-1950s, Andrei Kolmogorov, one of the giants of 20th century mathematics, publicly conjectured that there is no algorithm to multiply two n-digit numbers in o(n2) time. Kolmogorov organized a seminar at Moscow Uni- versity in 1960, where he restated his “n2 conjecture” and posed several related problems that he planned to discuss at future meetings. Almost exactly a week later, a 23-year-old student named Anatoli ̆ı Karatsuba presented Kolmogorov with a remarkable counterexample. According to Karastuba himself,
After the seminar I told Kolmogorov about the new algorithm and about the disproof of the n2 conjecture. Kolmogorov was very agitated because this contradicted his very plausible conjecture. At the next meeting of the semi- nar, Kolmogorov himself told the participants about my method, and at that point the seminar was terminated.
Karastuba observed that the middle coefficient bc+ad can be computed from the other two coefficients ac and bd using only one more recursive multiplication, via the following algebraic identity:
ac + bd − (a − b)(c − d) = bc + ad
This trick lets us replace the four recursive calls in the previous algorithm with
just three recursive calls, as shown below:
FastMultiply(x, y,n): if n = 1
return x · y else
m ← ⌈n/2⌉
a←⌊x/10m⌋; b←xmod10m c←⌊y/10m⌋; d←ymod10m
e ← FastMultiply(a, c, m)
f ←FastMultiply(b,d,m)
g ← FastMultiply(a − b, c − d, m)
return102me+10m(e+f −g)+f
〈〈x=10ma+b〉〉 〈〈y=10mc+d〉〉
20
The running time of Karatsuba’s FastMultiply algorithm follows the recurrence
T (n) ≤ 3T (⌈n/2⌉) + O(n)
1.9. Fast Multiplication
Again, we can safely ignore the ceiling in the recursive argument, and the recursion tree method transforms the recurrence into an increasing geometric series, but the new solution is only T(n) = O(nlog2 3) = O(n1.58496), a significant improvementoverourearlierquadratic-timealgorithm.10 Karatsuba’salgorithm arguably launched the design and analysis of algorithms as a formal field of study.
n
n/2 n/2 n/2
Figure 1.13. 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 even faster multiplication algorithms. Andrei Toom and Stephen Cook discovered an infinite family of algorithms that split any integer into k parts, each with n/k digits, and then compute the product using only 2k − 1 recursive multiplications. For any fixed k, the resulting 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 the discovery of the Fast Fourier transform.11 The basic FFT algorithm itself runs in O(nlogn) time; using FFTs for integer multiplication incurs some small additional overhead. The fastest integer multiplication algorithm currently known, published by David Harvey and Joris van der Hoeven in 2018, runs in O(n log n 4log∗ n) time. Here, log∗ n denotes the slowly growing iterated logarithm of n, which is the number of times one must take the logarithm of n before the value is less than 1:
1 if n ≤ 2, lg∗ n = 1 + lg∗(lg n) otherwise.
For all practical purposes, log∗ n ≤ 6. It has been conjectured that the best possible algorithm for multiply two n-digit numbers runs in Θ(n log n) time.
10My presentation simplifies the actual history slightly. In fact, Karatsuba proposed an algorithm based on the formula (a + c)(b + d) − ac − bd = bc + ad. This algorithm also runs in O(nlg3) 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 is due to Donald Knuth.
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
n/4
11See http://algorithms.wtf for lecture notes on Fast Fourier transforms.
21
1. RECURSION
1.10 Exponentiation
Given a number a and a positive integer n, suppose we want to compute an. The standard naïve method is a simple for-loop that performs n − 1 multiplications by a:
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 something that we know how to multiply. For example, the same algorithm can be used to compute powers modulo some finite number (an operation commonly used in 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 much time 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 2nd century bce, which uses the following simple recursive formula:
22
1
an = (an/2)2
(a⌊n/2⌋)2 · a
if n = 0 ifn>0andniseven otherwise
SlowPower(a, n): x←a
for i ← 2 to n x←x·a
return x
Pin ̇galaPower(a, n): if n = 1
return a else
x ← Pin ̇galaPower(a, ⌊n/2⌋) if n is even
return x · x else
return x · x · a
The total number of multiplications performed by this algorithm satisfies the recurrence 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 directly from the Egyptian peasant multiplication algorithm from the previous chapter,
1
an = (a2)n/2
(a2)⌊n/2⌋ · a
if n = 0 ifn>0andniseven otherwise
Exercises
by replacing addition with multiplication (and in particular, replacing duplation with squaring).
PeasantPower(a, n): if n = 1
return a else if n is even
return PeasantPower(a2, n/2) else
return PeasantPower(a2, ⌊n/2⌋) · a
This algorithm—which might reasonably be called “squaring and mediation”— also performs only O(logn) multiplications. Both of these algorithms are asymptotically optimal—any algorithm that computes an must perform at least Ω(log n) multiplications.
In fact, when n is a power of two, both of these algorithm are exactly optimal. However, there are slightly faster methods for other values of n. For example, Pin ̇galaPower and PeasantPower 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 of multiplications for a given exponent n can be computed efficiently.
Exercises Tower of Hanoi
1. 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 4).
(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.
23
1. RECURSION
(b) Forthefirstmove,movedisk1topeg1ifnisevenandtopeg2ifnis odd. Then repeatedly make the only legal move that does not undo 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.
• 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 the marks on a ruler, ρ(n) is sometimes called the ruler function.
Hanoi(n): i←1
while ρ(i) ≤ n
if n − i is even
move disk ρ(i) forward
〈〈0 → 1 → 2 → 0〉〉 〈〈0 → 2 → 1 → 0〉〉
else
move disk ρ(i) backward i←i+1
2. The Tower of Hanoi is a relatively recent descendant of a much older mechanical puzzle known as the Chinese linked rings, Baguenaudier, Car- dan’s Rings, Meleda, Patience, Tiring Irons, Prisoner’s Lock, Spin-Out, and many other names. This puzzle was already well known in both China and Europe by the 16th century. The Italian mathematician Luca Pacioli described the 7-ring puzzle and its solution in his unpublished treatise De Viribus Quantitatis, written between 1498 and 1506;12 only a few years later, the Ming-dynasty poet Yang Shen described the 9-ring puzzle as “a toy for women and children”. The puzzle is apocryphally attributed to a 2nd-century Chinese general, who gave the puzzle to his wife to occupy her time while he was away at war.
The Baguenaudier puzzle has many physical forms, but one of the most common 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 the
12De 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 15th-century mathematics, which included the first description of double-entry bookkeeping.
24
Exercises
Figure 1.14. The 7-ring Baguenaudier, from Récréations Mathématiques by Édouard Lucas (1891) (See Image Credits at the end of the book.)
rings as shown in the figure above; 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 ring and 0 otherwise. (Here we index the rings from right to left, as shown in the 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 5-ring puzzle:
11111 →1 11110 →3 11010 →1 11011 →2 11001 →1 11000
→5 01000 →1 01001 →2 01011 →1 01010 →3 01110
→1 01111 →2 01101 →1 01100 →4 00100 →1 00101
→2 00111 →1 00110 →3 00010 →1 00011 →2 00001 →1 00000
o(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 with graphs.]
(b) Describe an algorithm to solve the Baguenaudier puzzle. Your input is the number of rings n; your algorithm should print a reduced sequence of 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 function of n? Prove your answer is correct.
25
1. RECURSION
3. A less familiar chapter in the Tower of Hanoi’s history is its brief relocation of the temple from Benares to Pisa in the early 13th 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 Towers of Pisa and their attendant monks became famous, helping to establish Pisa as a dominant trading center on the Italian peninsula.
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 the priests to adopt a more relaxed rule: Any number of disks on the leaning needle 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 to be moved one at a time onto the leaning needle or between the two vertical needles.
Figure 1.15. The Towers of Pisa. In the fifth move, two disks are taken off the leaning needle.
Thanks to Fibonacci’s new rule, the priests could bring about the end of the universe somewhat faster from Pisa then they could than 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.13
Describe an algorithm to transfer a stack of n disks from one vertical needle to the other vertical needle, using the smallest possible number of moves. Exactly how many moves does your algorithm perform?
4. Consider the following restricted variants of the Tower of Hanoi puzzle. In each problem, the pegs are numbered 0, 1, and 2, and your task is to move a stack of n disks from peg 0 to peg 2, exactly as in problem 1.
(a) Suppose you are forbidden to move any disk directly between peg 1 and peg 2; every move must involve peg 0. Describe an algorithm to solve
13Portions of this story are actually true.
26
this version of the puzzle in as few moves as possible. Exactly how many moves does your algorithm make?
pn(b) Suppose you are only allowed to move disks from peg 0 to peg 2, from peg 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 to solve this version of the puzzle in as few moves as possible. How many moves does your algorithm make?
01234
56789
Figure 1.16. The first several moves in a counterclockwise Towers of Hanoi solution.
pn(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 version of the puzzle in as few moves as possible. How many moves does your algorithm make? [Hint: Matrices! This variant is considerably harder to analyze than the other two.]
5. 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, you are 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 a smaller 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 4(a).)
(b) Describe a recursive algorithm for the case k = n + 1 that requires at most O(n3) moves. [Hint: Use part (a).]
n(c) Describe a recursive algorithm for the case k = n + 1 that requires at most O(n2) moves. [Hint: Don’t use part (a).]
n(d) Describe a recursive algorithm for the case k = n that requires at most a polynomial number of moves. (What polynomial??)
Exercises
27
1. RECURSION
n(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 is bounded by a polynomial in n?
Recursion Trees
6. Use recursion trees to solve each of the following recurrences.
A(n) = 2A(n/4) + n D(n) = 3D(n/3) + n G(n) = 4G(n/2) + n
B(n) = 2B(n/4) + n E(n) = 3E(n/3) + n H(n) = 4H(n/2) + n
C(n) = 2C(n/4) + n2 F(n) = 3F(n/3) + n2 I(n) = 4I(n/2) + n2
7. 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)+n2
(l) L(n)=L(n/15)+L(n/10)+2L(n/6)+n
n8. Use recursion trees to solve each of the following recurrences. (m) M(n)=2M(n/2)+O(nlogn)
(n) N(n)=2N(n/2)+O(n/logn) (p) P(n)=nP(n)+n
(q) Q(n)=2nQ(2n)+n
Sorting
9. Suppose you are given a stack of n pancakes of different sizes. You want to sort 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.
28
Figure 1.17. 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 the worst case?14 [Hint: This problem has nothing to do with the Tower of Hanoi.]
(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?
10. 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 a quicksort 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 is always the second smallest element of the array. Designing this permutation requires intimate knowledge of the Partition subroutine.
(a)
n(b) 11. (a)
As a warm-up exercise, assume that the Partition subroutine is stable, meaning it preserves the existing order of all elements smaller than the pivot, and it preserves the existing order of all elements smaller than the pivot.
Assume that the Partition subroutine uses the specific algorithm listed on page 9, which is not stable.
Hey, Moe! Hey, Larry! Prove that the following algorithm actually sorts its input!
Exercises
StoogeSort(A[0 .. n − 1]) : if n = 2 and A[0] > A[1]
swap A[0] ↔ A[1] else if n > 2
m = ⌈2n/3⌉
StoogeSort(A[0 .. m − 1]) StoogeSort(A[n − m .. n − 1]) StoogeSort(A[0 .. m − 1])
(b)
Would StoogeSort still sort correctly if we replaced m = ⌈2n/3⌉ with m = ⌊2n/3⌋? Justify your answer.
14The 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.
29
1. RECURSION
(c) State a recurrence (including the base case(s)) for the number of comparisons executed by StoogeSort.
(d) Solve the recurrence, and prove that your solution is correct. [Hint: Ignore the ceiling.]
(e) Prove that the number of swaps executed by StoogeSort is at most n. 2
12. The following cruel and unusual sorting algorithm was proposed by Gary Miller:
Cruel(A[1 .. n]): if n > 1
Cruel(A[1 .. n/2]) Cruel(A[n/2 + 1 .. n]) Unusual(A[1 .. n])
Unusual(A[1 .. n]): if n = 2
if A[1] > A[2]
swap A[1] ↔ A[2]
else
〈〈the only comparison!〉〉 〈〈swap 2nd and 3rd quarters〉〉
〈〈recurse on left half 〉〉 〈〈recurse on right half〉〉 〈〈recurse on middle half〉〉
for i ← 1 to n/4
swap A[i + n/4] ↔ A[i + n/2]
Unusual(A[1 .. n/2]) Unusual(A[n/2 + 1 .. n]) Unusual(A[n/4 + 1 .. 3n/4])
30
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 Cruel correctly sorts any input array. [Hint: Consider an array that contains n/4 1s, n/4 2s, n/4 3s, and n/4 4s. Why is this special case enough?]
(b) Prove that Cruel would not correctly sort if we removed the for-loop from Unusual.
(c) Prove that Cruel would not correctly sort if we swapped the last two lines of Unusual.
(d) What is the running time of Unusual? Justify your answer.
(e) What is the running time of Cruel? Justify your answer.
13. An inversion in an array A[1 .. n] is a pair of indices (i, j) such that i < j and
A[i] > A[ j]. The number of inversions in an n-element array is between 0
(if the array is sorted) and n (if the array is sorted backward). Describe 2
and analyze an algorithm to count the number of inversions in an n-element array in O(n log n) time. [Hint: Modify mergesort.]
q4 p2
q1
p6 p7 q3 q5
Figure 1.18. Eleven intersecting pairs of segments with endpoints on parallel lines, and ten intersecting pairs of segments with endpoints on a circle.
p3 4
p q7
q6
p1
Exercises
14.(a) Supposeyouaregiventwosetsofnpoints,oneset{p1,p2,…,pn}onthe line y =0andtheotherset{q1,q2,…,qn}ontheline y =1. Createaset of 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 point qi. Describe and analyze a divide-and-conquer algorithm to determine how many pairs of these line segments intersect in O(n log2 n) time. [Hint: Use your solution to part (a).]
n(c) Describe an algorithm for part (b) that runs in O(n log n) time. [Hint: Use your solution from part (b)!]
p5 q2
15. (a)
p(b)
(c)
Describe an algorithm that sorts an input array A[1 .. n] by calling a subroutine SqrtSort(k), which sorts the subarray Ak + 1 .. k + n in place, given an arbitrary integer k between 0 and n − n as input. (To simplify the problem, assume that n is an integer.) Your algorithm is only allowed to inspect or modify the input array by calling SqrtSort; in particular, your algorithm must not directly compare, move, or copy array elements. How many times does your algorithm call SqrtSort in the worst case?
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 SqrtSort, prove that no algorithm can sort using o(f(n)) calls to SqrtSort.
Now suppose SqrtSort is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size n1/4. What is the worst-case running time of the resulting sorting algorithm? (To
q5 q1 q2 q4 q7 q3 q6
p1p7p4p3p6p2 p5
31
1. RECURSION
32
simplify the analysis, assume that the array size n has the form 22k , so that repeated square roots are always integers.)
Selection
16. Suppose we are given a set S of n items, each with a value and a weight. For any element x ∈ S, we define two subsets
• S
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
Describe and analyze an algorithm to compute the weighted median of 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 has value S[i] and weight W[i]. You may assume that all values are distinct and all weights are positive.
17. (a) (b)
Describe an algorithm to determine in O(n) time whether an arbitrary array A[1 .. n] contains more than n/4 copies of any value.
Describe and analyze an algorithm to determine, given an arbitrary array 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 function of 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.
18. 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 each internal node contains a comparison of the form “A[i] ≷ A[j]?” and each leaf contains an index into the array.
19. Consider the generalization of the Blum-Floyd-Pratt-Rivest-Tarjan Select algorithm shown in Figure 1.20, which partitions the input array into ⌈n/b⌉ blocks of size b, instead of ⌈n/5⌉ blocks of size 5, but is otherwise identical.
(a) State a recurrence for the running time of MombSelect, assuming that b is a constant (so the subroutine MedianOfB runs in O(1) time). In particular, how do the sizes of the recursive subproblems depend on the constant b? Consider even b and odd b separately.
Exercises
A[1]:A[2]
<>
A[1]:A[3] A[1]:A[3] <> <> A[2]:A[3] A[1] A[1] A[2]:A[3] <> <>
A[2] A[3] A[3] A[2]
Figure 1.19. Finding the median of a 3-element array using at most 3 comparisons
MombSelect(A[1..n],k):
if n ≤ b2
use brute force
else
m ← ⌈n/b⌉ for i ← 1 to m
M[i]←MedianOfB(A[b(i−1)+1..bi]) momb ← MombSelect(M[1..m],⌊m/2⌋)
r ←Partition(A[1..n],momb)
if k < r
return MombSelect(A[1..r −1],k)
else if k > r
return Mom b Select(A[ r + 1 .. n], k − r )
else
return momb
Figure 1.20. A parametrized family of selection algorithms; see problem 19.
(b) What is the worst-case running time of Mom1Select? [Hint: This is a trick question.]
pn(c) What is the worst-case running time of Mom2Select? [Hint: This is an unfair question!]
n(d) What is the worst-case running time of Mom3Select? Finding an upper bound on the running time is straightforward; the hard part is showing that this analysis is actually tight. [Hint: See problem 10.]
n(e) What is the worst-case running time of Mom4Select? Again, the hard part is showing that the analysis cannot be improved.15
15The median of four elements is either the second smallest or the second largest. In 2014, Ke Chen and Adrian Dumitrescu proved that if we modify Mom4Select to find second-smallest elements when k < n/2 and second-largest elements when k > n/2, the resulting algorithm runs in O(n) time! See their paper “Select with Groups of 3 or 4 Takes Linear Time” (WADS 2015, arXiv:1409.3600) for details.
33
1. RECURSION
(f) For any constants b ≥ 5, the algorithm MombSelect 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 median of b numbers. The exact value of M(b) is known only for b ≤ 13:
b 1 2 3 4 5 6 7 8 9 10 11 12 13 M(b) 0 1 3 4 6 8 10 12 14 16 18 20 23
For each b between 5 and 13, find an upper bound on the running time of MombSelect of the form T(n) ≤ αbn for some explicit constant αb. (For example, on page 18 we showed that α5 ≤ 16.)
(g) Which value of b yields the smallest constant αb? [Hint: This is a trick question!]
20. Prove that the variant of the Blum-Floyd-Pratt-Rivest-Tarjan Select algo- rithm shown in Figure 1.21, which uses an extra layer of small medians to choose the main pivot, runs in O(n) time.
MomomSelect(A[1 .. n], k):
if n ≤ 81
use brute force
else
m ← ⌈n/3⌉ for i ← 1 to m
M[i]←MedianOf3(A[3i−2..3i])
mm ← ⌈m/3⌉ for j ← 1 to mm
Mom[j]←MedianOf3(M[3j−2..3j]) momom ← MomomSelect(Mom[1 .. mm], ⌊mm/2⌋) r ← Partition(A[1 .. n], momom)
if k < r
return MomomSelect(A[1 .. r − 1], k)
else if k > r
return MomomSelect(A[r + 1 .. n], k − r)
else
return momom
34
Figure 1.21. Selection by median of moms; see problem 20).
21. (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 Θ(logn) 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).]
n(c) Now suppose we are given three sorted arrays A[1..n], B[1..n], and C [1 .. n], and an integer k. Describe an algorithm to find the kth smallest elementinA∪B∪C inO(logn)time.
(d) Finally,supposewearegivenatwodimensionalarrayA[1..m,1..n]in which 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 16 first.]
Arithmetic
22. In 1854, archaeologists discovered Sumerians clay tablets, carved around 2000bce, that list the squares of integers up to 59. This discovery led some scholars to conjecture that ancient Sumerians performed multiplication by reduction to squaring, using an identity like x · y = (x2 + y2 − (x − y)2)/2. Unfortunately, those same scholars are silent on how the Babylonians supposedly squared larger numbers. Four thousand years later, we can finally rescue these Sumerian mathematicians from their lives of drudgery through the power of recursion!
(a)
(b) n(c)
23. (a)
(b)
(c)
Describe a variant of Karatsuba’s algorithm that squares any n-digit number in O(nlg3) time, by reducing to squaring three ⌈n/2⌉-digit numbers. (Karatsuba actually did this in 1960.)
Describe a recursive algorithm that squares any n-digit number in O(nlog3 6) time, by reducing to squaring six ⌈n/3⌉-digit numbers.
Describe a recursive algorithm that squares any n-digit number in O(nlog3 5) time, by reducing to squaring only five (n/3 + O(1))-digit numbers. [Hint: Whatis(a+b+c)2+(a−b+c)2?]
Describe and analyze a variant of Karatsuba’s algorithm that multi- plies any m-digit number and any n-digit number, for any n ≥ m, in O(nmlg 3−1) time.
Describe an algorithm to compute the decimal representation of 2n in O(nlg3) time, using the algorithm from part (a) as a subroutine. (The standard algorithm that computes one digit at a time requires Θ(n2) time.)
Describe a divide-and-conquer algorithm to compute the decimal rep- resentation of an arbitrary n-bit binary number in O(nlg3) time. [Hint: Watch out for an extra log factor in the running time.]
Exercises
35
1. RECURSION
n(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)logn) time. [Hint: The analysis is the hard part; use a domain transformation.]
24. Consider the following classical recursive algorithm for computing the factorial n! of a non-negative integer n:
(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) Youranswerto(b)shouldconvinceyouthatthenumberofmultiplications is not a good estimate of the actual running time of Factorial. We can multiply any k-digit number and any l-digit number in O(k · l) time using either the lattice algorithm or duplation and mediation. What is the running time of Factorial if we use this multiplication algorithm as a subroutine?
(d) The following recursive algorithm also computes the factorial function, but using a different grouping of the multiplications:
What is the running time of Falling(n, n) if we use grade-school multi- plication? [Hint: As usual, ignore the floors and ceilings.]
(e) Describe and analyze a variant of Karastuba’s algorithm that multiplies any k-digit number and any l-digit number, for any k ≥ l, in O(k · llg 3−1) = O(k · l0.585) time.
n(f) What are the running times of Factorial(n) and Falling(n, n) if we use the modified Karatsuba multiplication from part (e)?
25. 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.
Falling(n, m): if m = 0
return 1 else if m = 1 return n
〈〈Compute n!/(n − m)!〉〉
else
return Falling(n, ⌊m/2⌋) · Falling(n − ⌊m/2⌋, ⌈m/2⌉)
36
Factorial(n): if n = 0
return 1 else
return n · Factorial(n − 1)
Euclid’s Elements, written around 300bc, describes the following recursive algorithm to compute gcd(x, y):16
(a) Prove that EuclidGCD correctly computes gcd(x, y). Specifically: i. Prove that EuclidGCD(x, y) divides both x and y.
ii. Prove that every divisor of x and y is a divisor of EuclidGCD(x, y).
(b) What is the worst-case running time of EuclidGCD(x, y), as a function of x and y? (Assume that computing x − y requires O(log x + log y) time.)
(c) Prove that the following algorithm also computes gcd(x, y):
(d) What is the worst-case running time of FastEuclidGCD(x, y), as a function 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):
Exercises
EuclidGCD(x, y): if x = y
return x else if x > y
return EuclidGCD(x − y, y) else
return EuclidGCD(x, y − x)
FastEuclidGCD(x, y): if x = y
return x else if x > y
return FastEuclidGCD(x mod y, y) else
return FastEuclidGCD(x, y mod x)
BinaryGCD(x, y): if x = y
return x
else if x and y are both even
return 2 · BinaryGCD(x/2, y/2) else if x is even
BinaryGCD(x/2, y) else if y is even
BinaryGCD(x, y/2) else if x > y
return BinaryGCD((x − y)/2, y) else
return BinaryGCD(x,(y − x)/2)
16Euclid’s algorithm is sometimes incorrectly described as the first recursive algorithm, or even the first nontrivial algorithm, even though the Egyptian duplation and mediation algorithm—which is both nontrivial and recursive—predates Euclid by at least 1500 years.
37
1. RECURSION
(f) What is the worst-case running time of FastEuclidGCD(x, y), as a functionof x and y? (Assumethatcomputing x−y takesO(logx+log y) time, and computing z/2 requires O(logz) time.)
Arrays
26. Suppose you are given a 2n × 2n chessboard 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 of 3 squares. Your input is the integer n and two n-bit integers representing the row 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.]
27. Youareavisitoratapoliticalconvention(orperhapsafacultymeeting)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; in particular, you will be summarily ejected from the convention if you ask. However, you can determine whether any pair of delegates belong to the same party by introducing them to each other. Members of the same political party always greet each other with smiles and friendly handshakes; members of different parties always greet each other with angry stares and insults.17
(a) Suppose more than half of the delegates belong to the same political party. Describe an efficient algorithm that identifies all members of this majority party.
(b) Now suppose there are more than two parties, but one party has a plurality: more people belong to that party than to any other party. Present a practical procedure to precisely pick the people from the plurality political party as parsimoniously as possible, presuming the plurality party is composed of at least p people. Pretty please.
28. Smullyan Island has three types of inhabitants: knights always speak the truth; knaves always lie; and normals sometimes speak the truth and sometimes don’t. Everyone on the island knows everyone else’s name and type (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:
38
17Real-world politics is much messier than this simplified model, but this is a theory book!
• 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 is
not.
• 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; in particular, you may not ask an inhabitant about their own type. Asking the same inhabitant the same question multiple times always yields the same answer, 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 to determine the type of every inhabitant.
29. Mostgraphicshardwareincludessupportforalow-leveloperationcalledblit, 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. This is 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 four n/2 × n/2 blocks, move each block to its proper position using a sequence of five 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.
Exercises
A
B
C
D
C
A
D
B
A
B
C
D
(a) (b) (c)
(d) (e)
5 blits recurse recurse 5 blits
Figure 1.22. Two algorithms for rotating a pixel map.
Prove that both versions of the algorithm are correct when n is a power
of 2.
Exactly how many blits does the algorithm perform when n is a power
of 2?
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?
What is your algorithm’s running time if a k × k blit takes O(k2) time? What if a k × k blit takes only O(k) time?
30. An
indices i and j such that A[(i − 1) mod n] < A[i] > A[(i + 1) mod n] and
array A[0 .. n − 1] of n distinct numbers is bitonic if there are unique
39
AB CD
BD AC
AB CD
1. RECURSION
40
Figure 1.23. The first 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,
469875123 isbitonic,but 369875124 isnotbitonic.
Describe and analyze an algorithm to find the smallest element in an n- element bitonic array in O(log n) time. You may assume that the numbers in the input array are distinct.
31. SupposewearegivenanarrayA[1..n]ofndistinctintegers,whichcouldbe positive, negative, or zero, sorted in increasing order so that A[1] < A[2] < ···
32. 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
We can obviously find a local minimum in O(n) time by scanning through the array. Describe and analyze an algorithm that finds a local minimum in O(log n) time. [Hint: With the given boundary conditions, the array must have at least one local minimum. Why?]
33. 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 in increasing order, the corresponding suffix A[k + 1 .. n] is sorted in increasing order, and A[n] < A[1].
For example, you might be given the following 16-element array (where k = 10):
9131618192328313742 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.
34. At the end of the second act of the action blockbuster Fast and Impossible
XIII3: The Last Guardians of Expendable Justice Reloaded, the villainous 4
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 shoot the 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 compute the Left and Right targets of each hero in O(n2) time using the following brute-force algorithm.
Exercises
WhoTargetsWhom(Ht[1 .. n]): for j ← 1 to n
〈〈Find the left target L[ j] for hero j〉〉 L[j]←None
for i ← 1 to j − 1
if Ht[i] > Ht[j] L[j] ← i
〈〈Find the right target R[ j] for hero j〉〉 R[j]←None
for k ← n down to j + 1
if Ht[k] > Ht[j] R[j] ← k
return L[1 .. n], R[1 .. n]
41
1. RECURSION
42
(a) Describe a divide-and-conquer algorithm that computes the output of WhoTargetsWhom in O(n log n) time.
(b) Prove that at least ⌊n/2⌋ of the n heroes are targets. That is, prove that the output arrays R[0 .. n − 1] and L[0 .. n − 1] contain at least ⌊n/2⌋ distinct values (other than None).
(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 then shoot their targets at the next signal. Eventually, only the shortest member of the Hero Crew/Alliance/Posse is left alive.18
Describe and analyze an algorithm to compute the number of rounds before Dr. Metaphor’s deadly process finally ends. For full credit, your algorithm should run in O(n) time.
35. You are a contestant on the hit game show “Beat Your Neighbors!” You are presented with an m × n grid of boxes, each containing a unique number. It costs $100 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-Ronitm, to which you are hopelessly addicted.
(a)
n(b)
pn(c) 36. (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?
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?
Prove that your solution to part (b) is optimal up to a constant factor.
Let n = 2l − 1 for some positive integer l. Suppose someone claims to hold an unsorted array A[1 .. n] of distinct l-bit strings; thus, exactly one l-bit string does not appear in A. Suppose further that the only way we can access A is by calling the function FetchBit(i, j), which returns the jth bit of the string A[i] in O(1) time. Describe an algorithm to find the missing string in A using only O(n) calls to FetchBit.
18In 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 the other n − 1 heroes with lifelike balloon sculptures. So, yeah, basically it’s Avengers: Endgame.
Exercises
n(b) Now suppose n = 2l − k for some positive integers k and l, and again we are given an array A[1 .. n] of distinct l-bit strings. Describe an algorithm to find the k strings that are missing from A using only O(n log k) calls to FetchBit.
Trees
37. 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 1.24 for an example.
Figure 1.24. The largest complete subtree of this binary tree has depth 3.
38. 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 child of 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 1.25 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 1.25. Deleting a central vertex in a 34-node binary tree, leaving subtrees with 14, 7, and 12 nodes.
43
1. RECURSION
39. (a)
(b)
(c) (d) n(e)
Professor George O’Jungle has a 27-node binary tree, in which every node is labeled with a unique letter of the Roman alphabet or the character &. Preorder and postorder traversals of the tree visit the nodes in the following order:
• Preorder: IQJHLEMVOTSBRGYZKCA&FPNUDWX
• Postorder: HEMLJVQSGYRZBTCPUDNFW&XAKOI Draw George’s binary tree.
Recall that a binary tree is full if every non-leaf node has exactly two children.
i. Describeandanalyzearecursivealgorithmtoreconstructanarbitrary 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.
Describe and analyze a recursive algorithm to reconstruct an arbitrary binary tree, given its preorder and inorder node sequences as input.
Describe and analyze a recursive algorithm to reconstruct an arbitrary binary search tree, given only its preorder node sequence.
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 is consistent with at least one binary tree.
40. Suppose we have n points scattered inside a two-dimensional box. A kd- tree19 recursively subdivides the points as follows. If the box contains no points 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 them 90 degrees. Thus, we alternate between splitting vertically and splitting horizontally at each level of recursion. The final empty boxes are called cells.
19The term “kd-tree” (pronounced “kay dee tree”) was originally an abbreviation for “k- dimensional tree”, but modern usage ignores this etymology, in part because nobody in their right 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, the La Brea Tar Pits, Sahara Desert, Mount Kilimanjaro, South Vietnam, East Timor, the Milky Way Galaxy, the City of Townsville, and self-driving automobiles.
44
Exercises
Figure 1.26. A kd-tree for 15 points. The dashed line crosses the four shaded cells.
(a) How many cells are there, as a function of n? Prove your answer is correct.
(b) In the worst case, exactly how many cells can a horizontal line cross, as a 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 that
f(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: Use part (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).]
n41. Bob Ratenbur, a new student in CS 225, is trying to write code to perform preorder, inorder, and postorder traversals of binary trees. Bob sort-of understands the basic idea behind the traversal algorithms, but whenever he actually tries to implement them, he keeps mixing up the recursive calls. Five minutes before the deadline, Bob frantically submits code with the following structure:
Each in this pseudocode hides one of the prefixes Pre, In, or Post. Moreover, each of the following function calls appears exactly once in Bob’s submitted code:
PreOrder(v): if v = Null
return else
print label(v) Order(left(v))
Order(right(v))
InOrder(v): if v = Null
return else
Order(left(v)) print label(v)
Order(right(v))
PostOrder(v): if v = Null
return else
Order(left(v))
Order(right(v)) print label(v)
45
1. RECURSION
PreOrder(left(v)) InOrder(left(v)) PostOrder(left(v))
PreOrder(right(v)) InOrder(right(v)) PostOrder(right(v))
Thus, there are precisely 36 possibilities for Bob’s code. Unfortunately, Bob accidentally deleted his source code after submitting the executable, so neither 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 helpfully parsed 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 AD
CG EB
IF
and your second algorithm should reconstruct the following code:
n42. 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 (1) T is empty, or (2) T satisfies the following recursive conditions:
46
PreOrder(v): if v = Null
return else
print label(v) PreOrder(left(v)) PostOrder(right(v))
InOrder(v): if v = Null
return else
PostOrder(left(v)) print label(v) PreOrder(right(v))
PostOrder(v): if v = Null
return else
InOrder(left(v)) InOrder(right(v)) print label(v)
Exercises
• 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.20
yx
y
CA
AB BC
• Swap the left and right subtrees of an arbitrary node. xx
AB BA
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 tree with distinct node values into a binary search tree, using at most O(n2) rotations and swaps. Figure 1.27 shows a sequence of eight operations that transforms a five-node binary tree into a binary search tree.
332234444
1412334253535225
524144151221313 555 11
Figure 1.27. “Sorting” a binary tree: rotate 2, rotate 2, swap 3, rotate 3, rotate 4, swap 3, rotate 2, swap 4.
Your algorithm is not allowed to directly modify parent or child pointers, 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, as long as that computation does not modify the tree; the running time of your algorithm is defined to be the number of rotations and swaps that it performs.
n(b) Describe an algorithm to transform an arbitrary n-node binary tree into a binary search tree, using at most O(n log n) rotations and swaps.
20Rotations 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 lecture notes on all of these data structures.
x
47
1. RECURSION
48
(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).
n(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.]