b. The recurrence relation for the number of weighing ()needed in
the worst case is as follows:
()=(d3e)+1 for 1(1) = 0
For =3
the recurrence becomes (3)=(3−1)+1Solving it by
backward substitutions yields (3)==log
3
11. a. Compute 26 ·47 by the multiplication à la russe algorithm:
26 47
12. a. Here are pseudocodes for the nonrecursive and recurisive implementa-
tions of multiplication à la russe
36
Algorithm Russe( )
//Implements multiplication à la russe nonrecursively
Algorithm RusseRec( )
//Implements multiplication à la russe recursively
//Input: Two positive integers and
//Output: The product of and
if mod 2 = 0 return RusseRec(22)
else if =1 return
else return RusseRec((−1)22)+
13. Using the fact that ()can be obtained by a one-bit left cyclic shift of
,wegetthefollowingfor=40:
(40) = (1010002) = 100012=17
15. a. Using the initial condition (1) = 1 and the recurrences (2)=
2()−1and (2+1)= 2()+1 forevenandoddvaluesof, respec-
tively, we obtain the following values of ()for =1215:
37
We’ll prove that this formula solves the recurrences of the Josephus prob-
lem for any nonnegative integer by induction on For the basis value
=0,wehave(20+0)=2·0+1=1 as it should for the initial con-
dition. Assuming that for a given nonnegative integer and for every
=01 2−1(2+)=2+1we need to show that
(2+1 +)=2+1 for =01 2+1 −1
and, using the induction’s assumption, we can continue as follows
2(2+)+1=2[2+1]+1=2+1
c. Let =(−10)2where the first binary digit is 1In the
’s representation used in part (b), =2
+ =(−10)2Further,
as proved in part (b),
38
Exercises 4.5
1. a. If we measure an instance size of computing the greatest common divi-
sor of and by the size of the second number ,byhowmuchcanthe
size decrease after one iteration of Euclid’s algorithm?
2. Apply quickselect to find the median of the list of numbers 9, 12, 5, 17,
20, 30, 8.
3. Write pseudocode for a nonrecursive implementation of quickselect.
7. a. Outline an algorithm for finding the largest key in a binary search tree.
Would you classify your algorithm as a variable-size-decrease algorithm?
b.Whatisthetimeefficiency class of your algorithm in the worst case?
9. Outline a variable-size-decrease algorithm for constructing an Eulerian
circuit in a connected graph with all vertices of even degrees.
10. Misere one-pile Nim Consider the so-called misere version of the one-
pile Nim, in which the player taking the last chip looses the game. All
11. Ba. Moldy chocolate Two payers take turns by breaking an ×choco–
late bar, which has one spoiled 1-by-1square. Each break must be a single
straight line cutting all the way across the bar along the boundaries be-
tween the squares. After each break, the player who broke the bar last
39
eats the piece that does not contain the spoiled corner. The player left
with the spoiled square loses the game. Is it better to go first or second
in this game?
12. BFlipping pancakes There are pancakes all of different sizes that are
stacked on top of each other. You are allowed to slip a flipper under
13. BYouneedtosearchforagivennumberinan×matrix in which
every row and every column is sorted in increasing order. Can you design
a()algorithm for this problem? [Laa10]
Hints to Exercises 4.5
1. a. The answer follows immediately from the formula underlying Euclid’s
algorithm.
4. Write an equation of the straight line through the points ( []) and
( []) and find the coordinate of the point on this line whose coor-
dinate is
5. Construct an array for which interpolation search decreases the remaining
subarray by one element on each iteration.
8. a. Consider separately three cases: (i) the key’s node is a leaf, (ii) the
key’s node has one child, (iii) the key’s node has two children.
b. Assume that you know a location of the key to be deleted.
9. Starting at an arbitrary vertex of the graph, traverse a sequence of its
untraversed edges until either all the edges are traversed or no untraversed
edge is available.
41
13. Start by comparing the search number with the last element in the first
row.
42
Solutions to Exercises 4.5
1. a. Since the algorithm uses the formula gcd( )=gcd( mod ),the
size of the new pair will be mod Hence it can be any integer between
0and−1Thus, the size can decrease by any number between 1 and
2. Since =7=d72e=4and −1=3Applying quickselect with
the Lomuto partitioning to the list 9, 12, 5, 17, 20, 30, 8, we obtain the
following partition
0123456
912 5 17 20 30 8
0123456
912 5 17 20 30 8
Since =2−1we proceed with the right part of the list:
012 3 4 5 6
012 3 4 5 6
43
3. a. Algorithm Quickselect([0 −1])
//Solves the selection problem by partition-based algorithm
//Input: An array [0 −1] of orderable elements and integer (1 ≤
≤)
//Output: The value of the kth smallest element in [0 −1]
←0; ←−1
b. call QuickselectRec([0 −1])where
Algorithm QuickselectRec([])
//Solves the selection problem by recursive partition-based algorithm
4. Using the standard form of an equation of the straight line through two
given points, we obtain
44
5. If =[]or =[]formula (4.4) will yield =and =, respec-
tively, and the search for will stop successfully after comparing with
[]If [][]
0(−[])(−)
[]−[]−;
Hence, if interpolation search does not stop on its current iteration, it
reduces the size of the array that remains to be investigated at least by
one. Therefore, its worst-case efficiency is in ()We want to show that
it is, in fact, in Θ()Consider, for example, array [0 −1] in which
[0] = 0 and []=−1for =12 −1If we search for =−15
Since
(−15)(−)
(−1) =(−1)(−)−05(−)
(−1) =(−)−05(−)
(−1) (−)
and
45
Therefore []=[−(+1)]=−1(unless =−1)implying that
=0and =−(+1)on the next (+1) iteration(If =−1the
assertion holds true for the next and last iteration, too: []=[0] = 0
implying that =0and =0)
6. a. We can solve the inequality log2log2+16as follows:
b. Using the formula log=log
ln we can compute the limit as
follows:
7. a. Recursively, go to the right subtree until a node with the empty right
subtree is reached; return the key of that node. We can consider this al-
gorithm as a variable-size-decrease algorithm: after each step to the right,
8. a. This is an important and well-known algorithm. Case 1: If a key to
be deleted is in a leaf, make the pointer from its parent to the key’s node
that child. (If the node to be deleted is the root with a single child, make
its child the new root.) Case 3: If a key to be deleted is in a node
with two children, its deletion can be done by the following three-stage
procedure. First, find the smallest key 0in the right subtree of the ’s
b. Consider, as an example of the worst case input, the task of delet-
ing the root from the binary tree obtained by successive insertions of keys
9. Starting at an arbitrary vertex of the graph, traverse a sequence of its
untraversed edges until no untraversed edge is available from the vertex
arrived at. The traversed path will be a circuit .Ifincludes all
10. If =1Player 1 (the player to move first) loses by definition of the
misere game because s/he has no choice but to take the last chip. If
2≤≤+1Player 1 wins by taking −1chips to leave Player 2 with
one chip. If =+2 = 1+(+1)Player 1 loses because any legal
11. The problem is equivalent to the game of Nim, with the piles represented
by the rows and columns of the bar between the spoiled square and the
bar’s edges. Thus, the Nim’s theory outlined in the section identifies
both winning positions and winning moves in this game. According to
this theory, an instance of Nim is a winning one (for the player to move
12. Here is a decrease-and-conquer algorithm for this problem. Repeat the
following until the problem is solved: Find the largest pancake that is out
of order. (If there is none, the problem is solved.) If it is not on the top of
the stack, slide the flipper under it and flip to put the largest pancake on
the top. Slide the flipper under the first-from-the-bottom pancake that
Consider an arbitrary stack of +1 pancakes. With two flips or less, the
algorithm puts the largest pancake at the bottom of the stack, where it
doesn’t participate in any further flips. Hence, the total number of flips
needed for any stack of +1pancakes is bounded above by
2+()=2+(2−3) = 2(+1)−3
13. Compare the search number with the last element in the first row. If they
match, stop. If the search number is smaller than the matrix element, the
former can’t be in the last column of the matrix, whose elements can be