This file contains the exercises, hints, and solutions for Chapter 7 of the
Exercises 7.1
1. Is it possible to exchange numeric values of two variables, say, and ,
without using any extra storage?
4. Is the distribution-counting algorithm stable?
5. Design a one-line algorithm for sorting any array of size whose values
are distinct integers from 1 to
7. BThe following technique, known as virtual initialization,providesa
time-efficient way to initialize just some elements of a given array [0−
1] so that for each of its elements, we can say in constant time whether it
has been initialized and, if it has been, with which value. This is done
a. Sketch the state of arrays [07][07]and [07] after the three
assignments
b. In general, how can we check with this scheme whether []has been
initialized and, if it has been, with which value?
1
8. Least distance sorting There are ten Egyptian stone statutes standing
9. a. Write a program for multiplying two sparse matrices, a ×matrix
and a ×matrix
Hints to Exercises 7.1
1. Yes, it is possible. How?
3. Trace the algorithm on the input given (see Figure 7.2 for an example).
5. Where will []be in the sorted array?
6. Take advantage of the standard traversals of such trees.
8. Start by finding the target positions for all the statures.
9. a. Use linked lists to hold nonzero elements of the matrices.
Solutions to Exercises 7.1
1. The following operations will exchange values of variables and :
←+//holds + holds
←−//holds + holds
2. Yes, it will work correctly for arrays with equal elements.
3. Input: A: b, c, d, c, b, a, a, b
Frequencies 2 3 2 1 Distribution values 2 5 7 8
[][07]
[7] = 257 8
4. Yes, it is stable because the algorithm scans its input right-to-left and puts
equal elements into their section of the sorted array right-to-left as well.
5. for ←0to −1do [[]−1] ←[]
4
if and only if either is an ancestor of (i.e., is on the simple path from
theroot’streeto)oris to the left of (i.e., and are not on the
same simple path from the root to a leaf and ()is to the left of ()
7. a. The following diagram depicts the results of these assignments (the
values of the unspecified elements in the arrays are undefined):
01234567
8. Count for each statue the total number of statues shorter than it, as it
is done by comparison counting sort. Then use these counts to move the
statues from their current positions =01 9to their target positions
[0][1]…,[9]For example, this can be done as follows.
9. n/a
10. Taking into account the board’s symmetries, there are 765 essentially dif-
ferent positions in this game..It is easier to use the minimax algorithm
Exercises 7.2
1. Apply Horspool’s algorithm to search for the pattern BAOBAB in the text
BESS_KNEW_ABOUT_BAOBABS
2. Consider the problem of searching for genes in DNA sequences using Hor-
spool’s algorithm. A DNA sequence consists of a text on the alphabet
{A,C,G,T} and the gene or gene segment is the pattern.
3. How many character comparisons will be made by Horspool’s algorithm
in searching for each of the following patterns in the binary text of 1000
zeros?
4. For searching in a text of length for a pattern of length (≥)with
Horspool’s algorithm, give an example of
a. worst-case input.
b. best-case input.
8. a. Would the Boyer-Moore algorithm work correctly with just the bad-
symbol table to guide pattern shifts?
b. Would the Boyer-Moore algorithm work correctly with just the good-
suffix table to guide pattern shifts?
11. You are given two strings and ,eachcharacters long. You have to
establish whether one of them is a right cyclic shift of the other. For exam-
ple, PLEA is a right cyclic rotation of LEAP, and vice versa. (Formally,
is a right cyclic shift of if can be obtained by concatenating the (−)–
character suffixofand the -character prefixoffor some 1≤≤)
8
Hints to Exercises 7.2
1. Trace the algorithm in the same way it is done in the section for another
instance of the string-matching problem.
4. Find an example of a binary string of length and a binary string of
length (≥)so that Horspool’s algorithm makes
5. It is logical to try a worst-case input for Horspool’s algorithm.
6. Can the algorithm shift the pattern by more than one position without
the possibility of missing another matching substring?
7. For each pattern, fill in the two shift tables and then determine the number
9
Solutions to Exercises 7.2
1. The shift table for the pattern BAOBAB in a text comprised of English
letters, the period, and a space will be
A B C D … O… Z . _
2. a. For the pattern TCCTATTCTT and the alphabet {A,C,G,T}, the shift
table looks as follows:
b. Below the text and the pattern, we list the characters of the text that
are aligned with the last Tof the pattern, along with the corresponding
number of character comparisons (both successful and unsuccessful) and
the shift size:
the text: TTATAGATCTCGTATTCTTTTATAGATCTCCTATTCTT
the pattern: TCCTATTCTT
T: 2 comparisons, shift 1
C: 1 comparison, shift 2
3. a. For the pattern 00001, the shift table is
10
The algorithm will make one unsuccessful comparison and then shift the
pattern one position to the right on each of its trials:
000000 00000
The algorithm will make four successful and one unsuccessful comparison
and then shift the pattern one position to the right on each of its trials:
000000 00000
10000
10000
etc.
10000
The total number of character comparisons will be =5·996 = 4980
c. For the pattern 01010, the shift table is
11
4. a. The worst case: e.g., searching for the pattern 10…0
|{z }
in the text of
5. Yes: e.g., for the pattern 100
|{z}
−1
and the text 00
|{z}
=−+1while
=(−+1)
6. We can shift the pattern exactly in the same manner as we would in the
7. a. For the pattern 00001, the shift tables will be filled as follows:
the bad-symbol table the good-suffixtable
the pattern 2
The total number of character comparisons will be =1·996 = 996
b. For the pattern 10000, the shift tables will be filled as follows:
the bad-symbol table the good-suffixtable
the pattern 2
12
c. For the pattern 01010, the shift tables will be filled as follows:
the bad-symbol table the good-suffixtable
the pattern 2
.
On each trial, the algorithm will make one successful and one unsuccessful
comparison. The shift’s size will be computed as the maximum of 1=
max{1(0) −11}=1and 2=2(1) = 4 , which is 4. If we count
Thus, the total number of character comparisons will be =2·249 = 498
8. a. Yes, the Boyer-Moore algorithm can get by with just the bad-symbol
shift table.
9. a. Horspool’s algorithm can also compare the remaining −1characters