Hints to Exercises 4.3
1. Use standard formulas for the numbers of these combinatorial objects. For
2. We traced the algorithms on smaller instances in the section.
3. See an outline of this algorithm in the section.
4. a. Trace the algorithm for =2;take advantage of this trace in tracing
the algorithm for =3and then use the latter for =4
5. We traced both algorithms on smaller instances in the section.
6. Tricks become boring after they have been given away.
7. This is not a difficult exercise because of the obvious way of getting bit
strings of length from bit strings of length −1
10. There are several decrease-and—conquer algorithms for this problem. They
are more subtle than one might expect. Generating combinations in a pre-
defined order (increasing, decreasing, lexicographic) helps with both a de-
21
Solutions to Exercises 4.3
1. Since 25! ≈15·1025it would take an unrealistically long time to generate
2. a. The permutations of {1234}generated by the bottom-up minimal-
change algorithm:
start 1
insert 2into 1 right to left 12 21
insert 3into 12 right to left 123 132 312
b. The permutations of {1234}generated by the Johnson-Trotter al-
gorithm. (Read horizontally; the largest mobile element is shown in bold.)
←
1
←
2
←
3
←
4
←
1
←
2
←
4
←
3
←
1
←
4
←
2
←
3
←
4
←
1
←
2
←
3
c. The permutations of {1234}generated in lexicographic order. (Read
horizontally.)
1234 1243 1324 1342 1423 1432
22
4. a. For =2:
12 21
b. Let ()be the number of times the algorithm writes a new per-
mutation (on completion of the recursive call when =1). We have the
following recurrence for ():
c. We have the following recurrence for the number of swaps ():
and substituting ()= ()
!to obtain the following recurrence:
()=(−1) + 1
(−1)! for 1(1) = 0
Solving the last recurrence by backward substitutions yields
23
5. Generate all the subsets of a four-element set ={1
2
3
4}bottom
up:
subsets
0∅
1∅{1}
6. Establish the correspondence between subsets of ={1 }and bit
7. Algorithm BitstringsRec()
//Generates recursively all the bit strings of a given length
//Input: A positive integer
8. Algorithm BitstringsNonrec()
//Generates nonrecursively all the bit strings of a given length
//Input: A positive integer
24
9. a. The Gray code for =3is given at the end of the section:
000 001 011 010 110 111 101 100.
b. Tracing the nonrecursive algorithm to generate the binary reflexive
Gray code of order 4given in the problem’s statement, we obtain the
following
10. Here is a recursive algorithm from “Problems on Algorithms” by Ian Par-
berry [Par95, p.120]:
25
11. a. Number the disks from 1 to in increasing order of their size. The
b. Use the correspondence described in part a between bit strings of
the binary reflected Gray code and the disk moves in the Tower of Hanoi
12. The problem can be solved by the following recursive algorithm for pushing
the buttons numbered from 1 to If =1and the light bulb is not turned
on,pushbutton1. If1and the light bulb is not turned on, push
Alternatively, since a switch can be in one of the two states, it can be
thought of as a bit in an -bit string in which 0 and 1 represent, say, the
initial and opposite states of the switch, respectively. The total number
26
use the sequence of the Gray code’s bit strings for guidance which buttons
to push: if the next bit string differs from its immediate predecessor in
27
Exercises 4.4
1. A stick inches long needs to be cut into 1-inch pieces. Outline an
2. Design a decrease-by-half algorithm for computing blog2cand determine
its time efficiency.
3. a. What is the largest number of key comparisons made by binary search
in searching for a key in the following array?
4. Estimate how many times faster an average successful search will be in a
sorted array of one million elements if it is done by binary search versus
sequential search.
5. The time efficiency of sequential search does not depend on whether a list
is implemented as an array or as a linked list. Is it also true for searching
a sorted list by binary search?
6. a. Design a version of binary search that uses only two-way compar-
isons such as ≤and =. Implement your algorithm in the language of
7. A version of the popular problem-solving task involves presenting people
with an array of 42 pictures–seven rows of six pictures each–and asking
8. Consider ternary search–the following algorithm for searching in a
sorted array [0 −1].If=1simply compare the search key
with the single element of the array; otherwise, search recursively by com-
paring with [b3c]and if is larger, compare it with [b23c]to
determine in which third of the array to continue the search.
a. What design technique is this algorithm based on?
9. An array [0 −2] contains −1integers from 1 to in increasing
order. (Thus one integer in this range is missing.) Design the most
efficient algorithm you can to find the missing integer and indicate its
time efficiency.
10. a. Write a pseudocode for the divide-into-three algorithm for the fake-coin
problem. Make sure that your algorithm handles properly all values of ,
11. a. Apply the Russian peasant algorithm to compute 26 ·47
b. From the standpoint of time efficiency, does it matter whether we
multiply by or by by the Russian peasant algorithm?
12. a. Write pseudocode for the Russian peasant multiplication algorithm.
29
b. discern a pattern in the solutions for the first fifteen values of and
prove its general validity.
30
Hints to Exercises 4.4
1. Take care of the length of the longest piece present.
4. Estimate the ratios of the number of key comparisons made by sequential
search to the average number made by binary search in successful searches.
5. How would you reach the middle element in a linked list?
7. Number the pictures and use this numbering in your questions.
8. The algorithm is quite similar to binary search, of course. In the worst
case, how many key comparisons does it make on each iteration and what
fraction of the array remains to be processed?
12. You may implement the algorithm either recursively or nonrecursively.
13. The fastest way to the answer the question is to use the formula that
exploits the binary representation of , which is mentioned at the end of
the section.
15. a. Use forward substitutions (see Appendix B) into the recurrence equa-
tions given in the text.
Solutions to Exercises 4.4
1. Since cutting several pieces of a given stick at the same time is allowed,
we need to concern ourselves only with finding a cutting algorithm that
reduces the size of the longest piece present to size 1. This implies that
2. Algorithm LogFloor ()
//Input: A positive integer
//Output: Returns blog2c
3. a. According to formula (4.5), (13) = dlog2(13 + 1)e=4
2(27) 9(81)
4. For the successful search, the ratio in question can be estimated as follows:
5. Unlike an array, where any element can be accessed in constant time,
6. a. Here is pseudocode of the algorithm in question.
Algorithm TwoWayBinary Search([0 −1])
//Implements binary search with two-way comparisons
//Input: A sorted array [0 −1] and a search key
7. Apply a two-way comparison version of binary search using the picture
numbering. That is, assuming that pictures are numbered from 1 to 42,
start with a question such as “Is the picture’s number 21?”The largest
8. a. The algorithm is based on the decrease-by-a constant factor (equal to
3) strategy.
b. ()=2+(3) for =3
(0)(1) = 1
c. (3)=2+(3−1)[sub. (3−1)=2+(3−2)]
9. The problem can be solved by the decrease-by-half algorithm that is based
on following observation. Compare the middle element []with +1:
if []=+1the missing number is larger than +1 and therefore
should be searched for in the second half of the array; otherwise (i.e., if
[]+1)it should be searched for in the first half of the array).
10. a. If is a multiple of 3 (i.e., mod 3 = 0)we can divide the coins into
three piles of 3coins each and weigh two of the piles. If =3+1
35