Data Structures and Algorithm Analysis in C++ (3rd Edition, Mark Allen Weiss) – Complete Solution Manual Overview

Data Structures and Algorithm Analysis in C++
Solution Manual，3rd Edition (Mark Allen
Weiss) (z-lib.org)


CONTENTS


Preface v

Chapter Introduction 1
1
Chapter Algorithm Analysis 5
2
Chapter Lists, Stacks, and Queues 9
3
Chapter Trees 29
4
Chapter Hashing 41
5
Chapter Priority Queues (Heaps) 45
6
Chapter Sorting 53
7
Chapter The Disjoint Set 59
8
Chapter Graph Algorithms 63
9
Chapter Algorithm Design Techniques 77
10
Chapter Amortized Analysis 87
11
Chapter Advanced Data Structures and 91
12 Implementation

,Perface

cluded in this manual are answers to many of the exercises in the textbook Data
Structures and Algorithm Analysis in C++, third edition, published by Addison-
Wesley. These answers reflect the state of the book in the first printing of the third
edition.
Specifically omitted are general programming questions and any question
whose solution is pointed to by a reference at the end of the chapter. Solutions
vary in degree of completeness; generally, minor details are left to the reader. For
clarity, the few code segments that are present are meant to be pseudo-C++ rather
than completely perfect code.
Errors can be reported to .




Chapter 1


Introduction


1.4 The general way to do this is to write a procedure with heading
void processFile( String fileName );

which opens fileName, does whatever processing is needed, and then closes it. If a line of
the form
#include SomeFile

is detected, then the call
processFile( SomeFile );

is made recursively. Self-referential includes can be detected by keeping a list of
files for which a call to processFile has not yet terminated, and checking this list

, before making a new call to processFile.
1.5 int ones( int n )
{
if( n < 2 )
return n;
return n % 2 + ones( n / 2 );
}

1.7 (a) The proof is by induction. The theorem is clearly true for 0 < X f 1, since it
is true for X = 1, and for X < 1, log X is negative. It is also easy to see that the
theorem holds for 1 < X f 2, since it is true for X = 2, and for X < 2, log X is at
most 1. Suppose the theorem is true for p < X f 2p (where p is a positive
integer), and consider any 2p < Y f 4p (p ≥ 1). Then log Y = 1 + log(Y/2) < 1 +
Y/2 < Y/2 + Y/2 f Y , where the first inequality follows by the inductive
hypothesis.
B 2X = A. Then
(b) ALet= = 2 . Thus log A = XB. Since X = log A, the theorem
B is
(2 )
proved.
1.8 (a) The sum is 4/3 and follows directly from the formula.
(b) S = 41 +42 2 + 3 + . . .. 4S = 1 + 2 + 3 + Subtracting the first equation from the
43 4 42
second
gives 3S = 14+ 142+ 2 + By part (a), 3S = 4/3 so S = 4/9.
1
(c) S = 4 +42 +4
43
9 + . . .. 4S =4 1 +42 4 +43 9 + 16 + Subtracting the first equation
from the
7 + . . .. Rewriting, i +
second gives 3S =41 +423 + 435 1 . Thus 3S =
Σ∞ Σ
∞
we get 3S = 2
i=0 i=0
2(4/9) + 4/3 = 20/9. Thus S =
20/27.
= iN . Follow the same method as in parts (a)–(c) to obtain a
(d) Let Σ
∞
in terms
SN formula
4
for S
of S i=0
N —1, SN—2, . . . , S0 and solve the recurrence. Solving the recurrence is very difficult.
Σ 1 Σ 1 LN/2 1
1.9 = —1] ≈ ln N — ln N/2 ≈ ln 2.
—



1

, 2 Chapter 1 Introduction


1.10 24 = 16 ≡ 1 (mod 5). (24)25 ≡ 125 (mod 5). Thus 2100 ≡ 1 (mod 5).
1.11 (a) Proof is by induction. The statement is clearly true for N = 1 and N = 2.
Assume true for
N = 1, 2, . . . , k. 1Σ Fi = Fi + Fk+1. By the induction hypothesis, the value
k+

Then Σ of the sum
on the right —2
i=1
i=
1 — 2, where the latter equality follows from the
is F definition of
the Fibonacci numbers. This proves the claim for N = k + 1, and hence for all N .
2
(b) As in the text, the proof is by induction. Observe that φ + 1 = φ . This implies
—1 —2
that φ + φ =
1. For N = 1 and N = 2, the statement is true. Assume the claim is true for N = 1,
2, . . . , k.
Fk+1 = Fk + Fk—1
by the definition and we can use the inductive hypothesis on the right-hand side,
obtaining
Fk+1 < φk + φk—1
< φ—1φk+1 + φ—2φk+1
Fk+1 < (φ—1 + φ—2)φk+1 < φk+1
and proving the theorem.
(c) See any of the advanced math references at the end of the chapter. The
derivation involves the use of generating functions.
N N N
Σ Σ Σ
1.12 (a (2i — 1) = 2 i — 1 = N(N + 1) — N = N 2.
)
(b) The easiest way to prove this is by induction. The case N = 1 is trivial.
Otherwise,
N +1 N
Σ 3 3 Σ
i = (N + 1) + i3
i=1 i=1

3 N 2(N +
= (N + 1)
+ 1)2 4
2
N2
= (N + 1) + (N + 1)
4
N 2 + 4N + 4
= (N + 1)2 4

(N + 1)2(N +
2)2 22
2
(N + 1)(N + 2)
2


1.15 class EmployeeLastNameCompare