Computer Algorithms, Third Edition,
Solutions to Selected Exercises
Sara Baase
Allen Van Gelder
February 25, 2000
ii
INTRODUCTION
This manual contains solutions for the selected exercises in Computer Algorithms: Introduction to Design and Analy-
sis, third edition, by Sara Baase and Allen Van Gelder.
Solutions manuals are intended primarily for instructors, but it is a fact that instructors sometimes put copies in
campus libraries or on their web pages for use by students. For instructors who prefer to have students work on
problems without access to solutions, we have chosen not to include all the exercises from the text in this manual. The
included exercises are listed in the table of contents. Roughly every other exercise is solved.
Some of the solutions were written specifically for this manual; others are adapted from solutions sets handed out
to students in classes we taught (written by ourselves, teaching assistants, and students).
Thus there is some inconsistency in the style and amount of detail in the solutions. Some may seem to be addressed
to instructors and some to students. We decided not to change these inconsistencies, in part because the manual will be
read by instructors and students. In some cases there is more detail, explanation, or justification than a student might
be expected to supply on a homework assignment.
Many of the solutions use the same pseudocode conventions used in the text, such as:
1. Block delimiters (“f” and “g”) are omitted. Block boundaries are indicated by indentation.
2. The keyword static is omitted from method (function and procedure) declarations. All methods declared in
the solutions are static.
3. Class name qualifiers are omitted from method (function and procedure) calls. For example, x = cons(z,
x) might be written when the Java syntax requires x = IntList.cons(z, x).
4. Keywords to control visibility, public, private, and protected, are omitted.
5. Mathematical relational operators “6=,” “,” and “” are usually written, instead of their keyboard versions.
Relational operators are used on types where the meaning is clear, such as String, even though this would be
invalid syntax in Java.
We thank Chuck Sanders for writing most of the solutions for Chapter 2 and for contributing many solutions in
Chapter 14. We thank Luo Hong, a graduate student at UC Santa Cruz, for assisting with several solutions in Chapters
9, 10, 11, and 13.
In a few cases the solutions given in this manual are affected by corrections and clarifications to the text. These
cases are indicated at the beginning of each affected solution. The up-to-date information on corrections and clarifica-
tions, along with other supplementary materials for students, can be found at these Internet sites:
ftp://ftp.aw.com/cseng/authors/baase
http://www-rohan.sdsu.edu/faculty/baase
http://www.cse.ucsc.edu/personnel/faculty/avg.html
cCopyright 2000 Sara Baase and Allen Van Gelder. All rights reserved.
Permission is granted for college and university instructors to make a reasonable number of copies, free of charge,
as needed to plan and administer their courses. Instructors are expected to exercise reasonable precautions against
further, unauthorized copies, whether on paper, electronic, or other media.
Permission is also granted for Addison-Wesley-Longman editorial, marketing, and sales staff to provide copies
free of charge to instructors and prospective instructors, and to make copies for their own use.
Other copies, whether paper, electronic, or other media, are prohibited without prior written consent of the authors.
List of Solved Exercises
1 Analyzing Algorithms and Problems: Principles and Examples
1.1 . . .
1.2 . . .
1.4 . . .
1.6 . . .
1.8 . . .
1.10 . .
1.12 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
1
2
2
2
3
3
3
1.13 . . . .
1.15 . . . .
1.18 . . . .
1.20 . . . .
1.22 . . . .
1.23 . . . .
1.25 . . . .
. .
. .
. .
. .
. .
. .
. .
3
4
4
4
4
4
5
1.28 . .
1.31 . .
1.33 . .
1.35 . .
1.37 . .
1.39 . .
1.42 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5
6
6
6
6
6
7
1.44 . . . .
1.46 . . . .
1.47 . . . .
1.48 . . . .
1.50 . . . .
. .
. .
. .
. .
. .
2 Data Abstraction and Basic Data Structures
2.2 . . .
2.4 . . .
2.6 . . .
. . . .
. . . .
. . . .
9
9
9
2.8 .
. . . .
2.10 . . . .
2.12 . . . .
. .
. .
. .
9
11
11
2.14 . .
2.16 . .
2.18 . .
. . . .
. . . .
. . . .
12
13
14
3 Recursion and Induction
3.2 . . .
3.4 . . .
. . . .
. . . .
17
17
3.6 .
3.8 .
. . . .
. . . .
. .
. .
17
18
3.10 . .
3.12 . .
. . . .
. . . .
18
18
4 Sorting
4.2 . . .
4.4 . . .
4.6 . . .
4.9 . . .
4.11 . .
4.13 . .
4.15 . .
4.17 . .
4.19 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
19
19
19
19
19
20
20
20
21
4.21 . . . .
4.23 . . . .
4.25 . . . .
4.26 . . . .
4.27 . . . .
4.29 . . . .
4.31 . . . .
4.34 . . . .
4.35 . . . .
. .
. .
. .
. .
. .
. .
. .
. .
. .
21
21
22
22
23
23
23
24
24
4.37 . .
4.40 . .
4.42 . .
4.44 . .
4.45 . .
4.46 . .
4.48 . .
4.49 . .
4.51 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
24
24
24
25
25
25
25
25
26
4.53 . . . .
4.55 . . . .
4.57 . . . .
4.59 . . . .
4.61 . . . .
4.63 . . . .
4.65 . . . .
. .
. .
. .
. .
. .
. .
. .
5 Selection and Adversary Arguments
5.2 . . .
5.4 . . .
5.6 . . .
. . . .
. . . .
. . . .
31
32
32
5.8 .
. . . .
5.10 . . . .
5.12 . . . .
. .
. .
. .
33
34
34
5.14 . .
5.16 . .
5.19 . .
. . . .
. . . .
. . . .
34
34
35
5.21 . . . .
5.22 . . . .
5.24 . . . .
. .
. .
. .
6 Dynamic Sets and Searching
6.1 . . .
6.2 . . .
6.4 . . .
6.6 . . .
6.8 . . .
6.10 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
39
39
40
40
41
41
6.12 . . . .
6.14 . . . .
6.16 . . . .
6.18 . . . .
6.20 . . . .
6.22 . . . .
. .
. .
. .
. .
. .
. .
41
43
45
45
45
46
6.24 . .
6.26 . .
6.28 . .
6.30 . .
6.32 . .
6.34 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
47
47
47
47
48
49
6.36 . . . .
6.37 . . . .
6.40 . . . .
. .
. .
. .
1
7
7
7
7
8
9
17
19
26
27
27
28
28
29
29
31
35
36
37
39
49
49
50
iv
List of Solved Exercises
7 Graphs and Graph Traversals
7.1 . . .
7.3 . . .
7.4 . . .
7.6 . . .
7.8 . . .
7.10 . .
7.12 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
51
51
51
51
51
52
52
7.14 . . . .
7.16 . . . .
7.18 . . . .
7.20 . . . .
7.22 . . . .
7.24 . . . .
7.27 . . . .
. .
. .
. .
. .
. .
. .
. .
53
53
53
54
54
54
57
7.28 . .
7.30 . .
7.32 . .
7.34 . .
7.35 . .
7.37 . .
7.39 . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
8 Graph Optimization Problems and Greedy Algorithms
8.1 . . .
8.3 . . .
8.5 . . .
8.7 . . .
. . . .
. . . .
. . . .
. . . .
63
63
63
64
8.8 .
. . . .
8.10 . . . .
8.12 . . . .
8.14 . . . .
. .
. .
. .
. .
64
64
64
64
8.16 . .
8.18 . .
8.20 . .
8.22 . .
. . . .
. . . .
. . . .
. . . .
57
57
57
57
58
59
59
65
65
65
67
7.40 . . . .
7.41 . . . .
7.43 . . . .
7.45 . . . .
7.47 . . . .
7.49 . . . .
. .
. .
. .
. .
. .
. .
8.24 . . . .
. .
8.26 . . . .
. .
8.27 . . . .
. .
9 Transitive Closure, All-Pairs Shortest Paths
9.2 . . .
9.4 . . .
9.6 . . .
. . . .
. . . .
. . . .
69
70
71
. . . .
9.7 .
9.8 .
. . . .
9.10 . . . .
. .
. .
. .
71
71
71
9.12 . .
9.14 . .
9.16 . .
. . . .
. . . .
. . . .
72
72
72
9.18 . . . .
. .
10 Dynamic Programming
10.2 . .
10.4 . .
10.5 . .
10.7 . .
. . . .
. . . .
. . . .
. . . .
11 String Matching
11.1 . .
11.2 . .
11.4 . .
11.6 . .
. . . .
. . . .
. . . .
. . . .
73
73
73
73
81
81
81
83
12 Polynomials and Matrices
10.9 . . . .
10.10 . . .
10.12 . . .
10.14 . . .
. .
. .
. .
. .
11.8 . . . .
11.10 . . .
11.12 . . .
11.15 . . .
. .
. .
. .
. .
73
74
75
75
84
84
84
84
10.16 .
10.18 .
10.19 .
10.21 .
. . . .
. . . .
. . . .
. . . .
11.17 .
11.19 .
11.21 .
11.23 .
. . . .
. . . .
. . . .
. . . .
75
76
77
78
84
85
85
85
10.23 . . .
10.26 . . .
. .
. .
11.25 . . .
. .
12.2 . .
12.4 . .
12.6 . .
. . . .
. . . .
. . . .
87
87
87
12.8 . . . .
12.10 . . .
12.12 . . .
. .
. .
. .
87
87
88
12.14 .
12.16 .
12.17 .
. . . .
. . . .
. . . .
88
88
88
13 N P -Complete Problems
13.2 . .
13.4 . .
13.6 . .
13.8 . .
13.10 .
13.12 .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
89
89
91
91
91
91
13.14 . . .
13.16 . . .
13.18 . . .
13.20 . . .
13.21 . . .
13.23 . . .
. .
. .
. .
. .
. .
. .
92
92
92
93
93
93
13.26 .
13.28 .
13.30 .
13.32 .
13.34 .
13.35 .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
93
93
94
94
96
96
13.37 . . .
13.39 . . .
13.42 . . .
13.44 . . .
13.47 . . .
13.49 . . .
. .
. .
. .
. .
. .
. .
51
59
59
59
60
60
61
63
67
67
67
69
72
73
78
79
81
86
87
89
96
96
98
99
99
99
List of Solved Exercises
v
13.51 .
13.53 .
. . . .
99
. . . . 100
13.54 . . .
13.55 . . .
. . 100
. . 100
13.57 .
13.59 .
. . . . 100
. . . . 101
13.61 . . .
. . 101
14 Parallel Algorithms
14.2 . .
14.4 . .
14.5 . .
14.7 . .
14.8 . .
. . . . 103
. . . . 103
. . . . 103
. . . . 104
. . . . 104
14.10 . . .
14.11 . . .
14.13 . . .
14.14 . . .
14.16 . . .
. . 104
. . 104
. . 104
. . 105
. . 105
14.18 .
14.19 .
14.20 .
14.22 .
14.24 .
. . . . 105
. . . . 106
. . . . 106
. . . . 106
. . . . 106
103
14.25 . . .
14.27 . . .
14.29 . . .
14.30 . . .
14.32 . . .
. . 106
. . 107
. . 107
. . 108
. . 108
vi
List of Solved Exercises
Analyzing Algorithms and Problems: Principles and Examples
Chapter 1
Section 1.2:
Java as an Algorithm Language
1.1
It is correct for instance fields whose type is an inner class to be declared before that inner class (as in Figure 1.2 in
the text) or after (as here). Appendix A.7 gives an alternative to spelling out all the instance fields in the copy methods
(functions).
class Personal
f
public static class Name
f
String firstName;
String middleName;
String lastName;
public static Name copy(Name n)
f
Name n2;
n2.firstName = n.firstName;
n2.middleName = n.middleName;
n2.lastName = n.lastName;
return n2;
g
g
public static class Address
f
String street;
String city;
String state;
public static Address copy(Address a) f/* similar to Name.copy() */ g
g
public static class PhoneNumber
f
int areaCode;
int prefix;
int number;
public static PhoneNumber copy(PhoneNumber n) f/* similar to Name.copy() */ g
g
Name name;
Address address;
PhoneNumber phone;
String eMail;
public static Personal copy(Personal p);
f
Personal p2;
p2.name = Name.copy(p.name);
p2.address = Address.copy(p.address);
p2.phone = PhoneNumber.copy(p.phone);
p2.eMail = p.eMail;
return p2;
g
g
2
Chapter 1 Analyzing Algorithms and Problems: Principles and Examples
Section 1.3: Mathematical Background
1.2
For 0 < k < n, we have
n 1
k =
n 1
k 1 =
Add them giving:
n 1!n k
=
n 1!
k!n 1 k!
n 1!
k 1!n k!
k!n k!
n 1!k
k!n k!
=
k
= n
n 1!n
k!n k!
k 1 and n
k = 0 in all these cases. If n < k, n 1
For 0 < n k we use the fact that a
the whole set.) Thus n 1
n 1
k 1 and n
b = 0 whenever a < b. (There is no way to choose more elements than there are in
k are both 0, confirming the equation. If n = k,
k are both 1, again confirming the equation. (We need the fact that 0! = 1 when n = k = 1.)
1.4
It suffices to show:
Consider b raised to each side.
So left side = right side.
logc xlogb c = logb x:
bleft side = blogb clogc x = blogb clogc x = clogc x = x
bright side = blogb x = x
1.6
Let x = dlgn 1e. The solution is based on the fact that 2x 1 < n 1 2x.
x = 0;
twoToTheX = 1;
while (twoToTheX < n+1)
x += 1;
twoToTheX *= 2;
return x;
The values computed by this procedure for small n and the approximate values of lgn 1 are:
n
0
1
2
3
4
5
6
7
8
9
x
0
1
2
2
3
3
3
3
4
4
lgn 1
0.0
1.0
1.6
2.0
2.3
2.6
2.8
3.0
3.2
3.3