Type:
Solution Manual
Resource:
Data Structures and Algorithm Analysis in Java
Edition:
3rd Edition
Author(s):
Mark A. Weiss
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
public static 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 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 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 2p (where p is a positive integer), and consider any 2p < Y 4p (p 1). Then log Y = 1 + log(Y/2)< 1 + Y/2 < Y/2 + Y/2 Y, where the first inequality follows by the inductive hypothesis. (b) Let 2X = A. Then AB = (2X)B = 2XB. Thus log AB = XB. Since X = log A, the theorem is proved.
1.8
(a) The sum is 4/3 and follows directly from the formula. (b) S = 14 + 22 + 33 + 4
4
3S = 1 + 14 + 22 +
(c) S = 14 + 42 + 93 +
..
. Subtracting the first equation from the second gives
4
. By part (a), 3S = 4/3 so S = 4/9.
4
4
. 4S = 1 + 24 + 32 +
4
. 4S = 1 + 44 + 92 + 163 + 4
4
. Subtracting the first equation from the second gives
3S = 1 + 34 + 52 + 73 + 4
4
. Rewriting, we get 3S = 2 ii + 1i . Thus 3S = 2(4/9) + 4/3 = 20/9. Thus S = i =0
4
i =0
4
20/27.
(d) Let SN = i i . Follow the same method as in parts (a) – (c) to obtain a formula for SN in terms of SN–1, N
4
i =0
SN–2,..., S0 and solve the recurrence. Solving the recurrence is very difficult. N
1.9
i = N / 2
1 = i
N
i =1
1 − i
N / 2 −1
1i ln N − ln N /2 ln 2. i =1
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. k +1
k
i =1
i =1
Then Fi = Fi + Fk + 1. By the induction hypothesis, the value of the sum on the right is Fk+2 – 2 + Fk+1 = Fk+3 – 2, where the latter equality follows from the definition of the Fibonacci numbers. This proves the claim for N = k + 1, and hence for all N. (b) As in the text, the proof is by induction. Observe that + 1 = 2. This implies that –1 + –2 = 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. 1.12
N
N
N
i =1
i =1
i =1
(a) (2i − 1) = 2 i − 1 = N(N + 1) – N = N2. (b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,
..
N +1
N
i =1
i =1
i3 = ( N + 1)3 + i3 = ( N + 1)3 +
N 2 ( N + 1) 2 4
N2 = ( N + 1) 2 + ( N + 1) 4 2 N + 4N + 4 = ( N + 1) 2 4 =
( N + 1) 2 ( N + 2) 2 22
( N + 1) ( N + 2) = 2 N +1 = i i =1
..
2
2
CHAPTER 2
Algorithm Analysis 2.1
2/N, 37,
N , N, N log log N, N log N, N log(N2), N log2 N, N1.5, N2, N2 log N, N3, 2N/2, 2N.
N log N and N log (N2) grow at the same rate. 2.2
(a) True. (b) False. A counterexample is T1(N) = 2N, T2(N) = N, and f (N) = N. (c) False. A counterexample is T1(N) = N2, T2(N) = N, and f (N) = N2. (d) False. The same counterexample as in part (c) applies.
2.3
We claim that N log N is the slower growing function. To see this, suppose otherwise. Then, N
log N
would grow slower than log N. Taking logs of both sides, we find that, under this assumption,
/ log N log N grows slower than log log N. But the first expression simplifies to log N . If L = log N, then we are claiming that L grows slower than log L, or equivalently, that 2L grows slower than log2 L. But we know that log2 L = o(L), so the original assumption is false, proving the claim. 2.4
Clearly, log k1 N = o(log k2 N ) if k1 < k2, so we need to worry only about positive integers. The claim is clearly true for k = 0 and k = 1. Suppose it is true for k < i. Then, by L’Hôpital’s rule,
logi N logi −1 N = lim i N → N → N N lim
The second limit is zero by the inductive hypothesis, proving the claim. 2.5
Let f(N) = 1 when N is even, and N when N is odd. Likewise, let g(N) = 1 when N is odd, and N when N is even. Then the ratio f(N)/g(N) oscillates between 0 and inf.
2.6
(a) 22
N
(b) O(log log D) 2.7
For all these programs, the following analysis will agree with a simulation: (I) The running time is O(N). (II) The running time is O(N2).
.