Answer question 6.98 from the textbook Discrete Mathematics for Computer Science by David Liben-Nowell
646 CHAPTER 6. ANALYSIS OF ALGORITHMS Figure 6.41: Four algorithms for the Fibonaccis. The values and satisfy fn - see Example 6.28. fibClever(n): fibNaive(n): 1: if n=0 or n= 1 then 2: return 1 3: else 4: return fibNaive(n -1) fibMedium(n): 1:,fn-1):-helper(n) 2: return f 1: return explon VS exp(b, n): 1: if n=0 then 2: return 1 3: else helper(n) 1: if n=0 then 2: return (1, undefined) 3: else if n=1 then 4: return (1,1) 5: else 6: fn-1,fn-2) : helper(n-1) 7: return n-1+n-2n-1) fibNaive(n -2) fibMatrix(n): 1: Compute (using repeated 5: if n is odd then 6: return bs s 7: squaring) | | else 1 0 11 return ss | 2: return x Recall that the Fibonacci numbers are defined by the recurrence fi 2 1andfn f-1+fn-2. The next several exercises refer to this recurrence and the algorithms for computing the Fibonacci numbers in Figure 6.41 6.95 First, a warmup unrelated to the algorithms in Figure 6.41: prove by induction that fn 2 6.96 Prove that fibNaive(n -k) appears a total of fic+1 times in the call tree for fibNaive(n). 6.97 Write down and solve a recurrence for the running time of helper (and therefore fibMedium). 6.98 Write down and solve a recurrence for the running time of exp (and therefore fibClever). 6.99 The reference to "repeated squaring" in fibMatrix is precisely the same as the idea of exp. Imple- ment fibMatrix using this idea in a programming language of your choice. (See Exercise 5.56.) 646 CHAPTER 6. ANALYSIS OF ALGORITHMS Figure 6.41: Four algorithms for the Fibonaccis. The values and satisfy fn - see Example 6.28. fibClever(n): fibNaive(n): 1: if n=0 or n= 1 then 2: return 1 3: else 4: return fibNaive(n -1) fibMedium(n): 1:,fn-1):-helper(n) 2: return f 1: return explon VS exp(b, n): 1: if n=0 then 2: return 1 3: else helper(n) 1: if n=0 then 2: return (1, undefined) 3: else if n=1 then 4: return (1,1) 5: else 6: fn-1,fn-2) : helper(n-1) 7: return n-1+n-2n-1) fibNaive(n -2) fibMatrix(n): 1: Compute (using repeated 5: if n is odd then 6: return bs s 7: squaring) | | else 1 0 11 return ss | 2: return x Recall that the Fibonacci numbers are defined by the recurrence fi 2 1andfn f-1+fn-2. The next several exercises refer to this recurrence and the algorithms for computing the Fibonacci numbers in Figure 6.41 6.95 First, a warmup unrelated to the algorithms in Figure 6.41: prove by induction that fn 2 6.96 Prove that fibNaive(n -k) appears a total of fic+1 times in the call tree for fibNaive(n). 6.97 Write down and solve a recurrence for the running time of helper (and therefore fibMedium). 6.98 Write down and solve a recurrence for the running time of exp (and therefore fibClever). 6.99 The reference to "repeated squaring" in fibMatrix is precisely the same as the idea of exp. Imple- ment fibMatrix using this idea in a programming language of your choice. (See Exercise 5.56.)
