This file contains the exercises, hints, and solutions for Chapter 5 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3d edition, by
Exercises 5.1
1. a. Write pseudocode for a divide-and-conquer algorithm for finding the
position of the largest element in an array of numbers.
2. a. Write pseudocode for a divide-and-conquer algorithm for finding values
of both the largest and smallest elements in an array of numbers.
3. a. Write pseudocode for a divide-and-conquer algorithm for the exponen-
tiation problem of computing where is a positive integer.
b. Set up and solve a recurrence relation for the number of multipli-
cations made by this algorithm.
4. As mentioned in Chapter 2, logarithm bases are irrelevant in most contexts
arising in analyzing an algorithm’s efficiency class. Is it true for both
assertions of the Master Theorem that include logarithms?
6. Apply mergesort to sort the list E, X, A, M, P, L, E in alphabetical
order.
7. Is mergesort a stable sorting algorithm?
8. a. Solve the recurrence relation for the number of key comparisons made
by mergesort in the worst case. (You may assume that =2
)
9. Let [0 −1] be an array of real numbers. A pair ([][]) is said
to be an inversion if these numbers are out of order, i.e., but
[][]Design an (log )algorithm for counting the number of
inversions.
10. One can implement mergesort without a recursion by starting with merg-
ing adjacent elements of a given array, then merging sorted pairs, and so
on. Implement this bottom-up version of mergesort in the language of
your choice.
11. Tromino puzzle A tromino is an L-shaped tile formed by adjacent 1-
2
Hints to Exercises 5.1
1. In more than one respect, this question is similar to the divide-and-conquer
computation of the sum of numbers.
4. Look at the notations used in the theorem’s statement.
5. Apply the Master Theorem.
c. Do not forget to include key moves made both before the split and
during the merging.
9. Modify mergesort to solve the problem.
3
Solutions to Exercises 5.1
1. a. Call Algorithm MaxIndex ( 0−1) where
Algorithm MaxIndex( )
b. This algorithm returns the index of the leftmost largest element.
c. The recurrence for the number of element comparisons is
()=(d2e)+(b2c)+1 for 1(1) = 0
Solving it by backward substitutions for =2
yields the following:
We can verify that ()=−1satisfies, in fact, the recurrence for
every value of 1by substituting it into the recurrence equation and
considering separately the even (=2)and odd (=2+1) cases. Let
=2 where 0Then the left-hand side of the recurrence equation
is −1=2−1The right-hand side is
4
2. a. Call Algorithm MinMax ( 0−1minval, maxval)where
Algorithm MinMax( minval, maxval)
//Finds the values of the smallest and largest elements in a given subarray
//Input: A portion of array [0 −1] between indices and (≤)
//Output: The values of the smallest and largest elements in []
//assigned to minval and maxval, respectively
b. Assuming for simplicity that =2
we obtain the following recurrence
for the number of element comparisons ():
()=2(2) + 2 for 2(2) = 1(1) = 0
Solving it by backward substitutions for =2
≥1yields the following:
5
optimal in terms of the number of comparisons made. As a practical
matter, however, it might not be faster than the brute-force algorithm
3. a. The following divide-and-conquer algorithm for computing is based
on the formula =b2cd2]:
b. The recurrence for the number of multiplications is
4. For the second case, where the solution’s class is indicated as Θ(log )
the logarithm’s base could change the function by a constant multiple only
5. The applications of the Master Theorem yield the following.
a. ()=4(2) + Here, =4=2and =1Since
()∈Θ(log24)=Θ(2)
6
6. Here is a trace of mergesort applied to the input given:
E X A M P L E
E X A M P L E
7. Mergesort is stable, provided its implementation employs the comparison
≤in merging. Indeed, assume that we have two elements of the same
value in positions and ,in a subarray before its two (sorted) halves
7
8. a. The recurrence for the number of comparisons in the worst case, which
was given in Section 5.1, is
()=2(2) + −1for 1(and =2
)
(1) = 0
Solving it by backward substitutions yields the following:
b. The recurrence for the number of comparisons on best-case inputs (e.g.,
lists sorted in ascending or descending order) is
()=2(2) + 2for 1(and =2
)
(1) = 0
Thus,
c. If 1the algorithm copies b2c+d2e=elements first and then
makes more moves during the merging stage. This yields the following
recurrence for the number of moves ():
8
5. Let ModifiedMergesort be a mergesort modified to return the number of
inversions in its input array [0 −1] in addition to sorting it. Obvi-
ously, for an array of size 1, ModifiedMergesort ([0]) should return 0. Let
and be the number of inversions returned by ModifiedMerge–
10. n/a
11. If =1each of the four possible 2×2boards with a missing square can
be covered in the obvious fashion by a single L-tromino. For 1we can
always place one L-tromino at the center of the 2×2chessboard with
Exercises 5.2
1. Apply quicksort to sort the list in alphabetical order.
2. For the partitioning procedure outlined in this section:
a. Prove that if the scanning indices stop while pointing to the same
3. Is quicksort a stable sorting algorithm?
4. Give an example of an array of elements for which the sentinel mentioned
in the text is actually needed. What should be its value? Also explain
why a single sentinel suffices for any input.
5. For the version of quicksort given in this section:
6. a. For quicksort with the median-of-three pivot selection, are strictly in-
creasing arrays the worst-case input, the best-case input, or neither?
b. Answer the same question for strictly decreasing arrays.
8. Design an algorithm to rearrange elements of a given array of real num-
bers so that all its negative elements precede all its positive elements.
Your algorithm should be both time efficient and space efficient.
10
10. Implement quicksort in the language of your choice. Run your program on
11. INuts and bolts Youaregivenacollectionofbolts of different widths
and corresponding nuts. You are allowed to try a nut and bolt together,
from which you can determine whether the nut is larger than the bolt,
Hints to Exercises 5.2
1. We traced the algorithm on another instance in the section.
5. Study what the section’s version of quicksort does on such arrays. You
should base your answers on the number of key comparisons, of course.
6. Where will splits occur on the inputs in question?
7. a. Computing the ratio 2(log2)for =10
6is incorrect.
Solutions to Exercises 5.2
1. Applying the version of quicksort given in Section 5.2, we get the follow-
ing:
0123 456
E
AM P L
M
L
M
X
M
X
M
X
LMPX
13
2. a. Let =be the coinciding values of the scanning indices. Accord-
ing to the rules for stopping the (left-to-right) and (right-to-left) scans,
3. Consider how quicksort works on a two-element array of equal values 1=
2:
4. With the pivot being the leftmost element, the left-to-right scan will get
out of bounds if and only if the pivot is larger than all the other elements.
Appending a sentinel of value equal [0] (or larger than [0]) after the
5. a. Arrays composed of all equal elements constitute the best case because
all the splits will happen in the middle of corresponding subarrays.
6. The best case for both questions. For either a strictly increasing or
strictly decreasing subarray, the median of the first, last, and middle values
7. a. The average case estimations for the number of comparisons made by
quicksort and insertion sort are 2ln and 24respectively. Hence,
14
8. The following algorithm uses the partition idea similar to that of quicksort,
although it’s implemented somewhat differently. Namely, on each iter-
ation the algorithm maintains three sections (possibly empty) in a given
array: all the elements in [0−1] are negative, all the elements in []
are unknown, and all the elements in [+1]are nonnegative:
9. The following algorithm uses the partition idea similar to that of quick-
sort. (See also a simpler 2-color version of this problem in Problem 8 in
these exercises.) On each iteration, the algorithm maintains four sections
(possibly empty) in a given array: all the elements in [0 −1] are filled
with R’s, all the elements in [−1] are filled with W’s, all the elements
On each iteration, the algorithm shrinks the size of the unknown section
by one element either from the left or from the right.
Algorithm DutchFlag([0 −1])
b. One can partition an array in three subarrays–the elements that are
10. n/a
11. Randomly select a nut and try each of the bolts for it to find the matching
bolt and separate the bolts that are smaller and larger than the selected
nut into two disjoint sets. Then try each of the unmatched nuts against
the matched bolt to separate those that are larger from those that are
16
Exercises 5.3
1. Design a divide-and-conquer algorithm for computing the number of levels
2. The following algorithm seeks to compute the number of leaves in a binary
tree.
3. Can you compute the height of a binary tree with the same assympotic
efficiency as the section’s divide-and-conquer algorithm but without us-
ing a stack explicitly or implicitly? Of course, you may use a different
algorithm althogether.
6. Write pseudocode for one of the classic traversal algorithms (preorder,
inorder, and postorder) for binary trees. Assuming that your algorithm
is recursive, find the number of recursive calls made.
8. a. Draw a binary tree with 10 nodes labeled 0, 1, …, 9 in such a way that
the inorder and postorder traversals of the tree yield the following lists: 9,
3, 1, 0, 4, 2, 7, 6, 8, 5 (inorder) and 9, 1, 4, 0, 3, 6, 7, 5, 8, 2 (postorder).
9. The internal path length of an extended binary tree is defined as the
sum of the lengths of the paths–taken over all internal nodes–from the
10. Write a program for computing the internal path length of an extended
binary tree. Use it to investigate empirically the average number of key
comparisons for searching in a randomly generated binary search tree.
11. Chocolate bar puzzle Given an -by-chocolate bar, you need to break
Hints to Exercises 5.3
1. The problem is almost identical to the one discussed in the section.
5. This is a standard exercise that you have probably done in your data
structures course. With the traversal definitions given at the end of
the section, you should be able to trace them even if you have never
encountered these algorithms before.
6. Your pseudocode can simply mirror the traversal definition.
7. If you do not know the answer to this important question, you may want
to check the results of the traversals on a small binary search tree. For a
19