Homework 4 (assigned April 23, due May 6)

Reading: Read CLRS chapters 8 and 9.

Written assignment: Solve the following "Do" exercises and assigned problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both "Do" exercises and problems.

"Do" Exercise (not to be handed in):

1. A tournament tree is a complete binary tree reflecting results of a single-elimination tournament: its leaves represent n players entering the tournament, and each internal node represents a winner of a match played by the players represented by the children of this node. The winner of the tournament is represented by the root of the tree.
   • What is the total number of games played in such a tournament?
   • How many rounds are there in such a tournament?
   • Design an efficient algorithm to determine the second best player using the information produced by the tournament. How many extra games does your algorithm require?

Problems (to be handed in):

1. Simultaneous max and min
   Describe an algorithm that uses at most 3 × floor[n/2] comparisons to simultaneously find the largest and smallest elements in an array of n numbers. Write pseudocode for your algorithm and justify its running time. (20 points)

2. Simultaneous smallest two
   Show that the two smallest numbers in a list of n numbers can be found with n + ceiling[lg n] - 2 comparisons in the worst case. (20 points)

3. Algorithm design
   
   1. Design a recursive algorithm for computing 2ⁿ for any nonnegative integer n that is based on the formula 2ⁿ = 2^n-1 + 2^n-1. Write pseudocode for your algorithm. (10 points)
   2. Write a recurrence for the number of additions made by your algorithm from part (1) and solve this recurrence. (5 points)
   3. Is your algorithm from part (1) an efficient algorithm for solving the problem of computing 2ⁿ? Present a second algorithm for solving this problem that is more efficient than the first. Clearly and concisely describe the steps that your second algorithm makes. (10 points)

4. Computing Fibonacci numbers
   Revision (5/1/08): Turn this problem in with Homework *6*, on May 13, as a bonus point problem.
   Note: The nth Fibonacci number satisfies the equality F_n = (φⁿ - φ'ⁿ)/√5, where φ = (1 + √5)/2 and φ' = (1 - √5)/2. See the above "Do" exercise.

   The Fibonacci numbers are defined by the following recurrence:

   F₀ = 0,
   F₁ = 1,
   F_n = F_n-1 + F_n-2 for n ≥ 2. We can use this recurrence to obtain the following recursive algorithm for computing the nth Fibonacci number F(n):
       F(n)
       01 if n = 0
       02       then return 0
       03 else if n = 1
       04       then return 1
       05 return F(n - 1) + F(n - 2)
   This algorithm is correct, since it directly implements the definition of the Fibonacci numbers. To analyze its cost, let A(n) be the number of additions peformed by the algorithm in computing F(n). Assume that all operations take unit time.
   1. Give a recurrence for A(n), and use the substitution method to show that A(n) = O(F_n). (10 points)
   2. Show that A(n) = Ω(F_n), and hence, that A(n) = Θ(F_n). (5 points)

   The following is an alternative algorithm for computing the nth Fibonacci number which computes the successive elements of the Fibonacci sequence iteratively:
       Fib(n)
       01 Fib(0) <- 0
       02 Fib(1) <- 1
       03 for i ← 2 to n do
       04       Fib(i) <- Fib(i - 1) + Fib(i - 2)
       05 return Fib(n)

   1. How many additions does this algorithm make on input n? (5 points)
   2. Which of these two algorithms for computing the nth Fibonacci number is faster? Justify your answer. (5 points)