Computer Science 477/677: Design and Analysis of Algorithms

Spring 2001

Homework Assignment 6.

Due March 21, 2001

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

Do not write your homework as a computer file and turn in a printout.

• Work exercise 16.1-1 on page 308 of your textbook.
• Consider the following two recursive definitions of Fibonacci numbers:
  Definition 1:
  • F(0) = 0
  • F(1) = 1
  • F(i) = F(i-2) + F(i-1) for i > 1
  Definition 2:
  • F(0) = 0
  • F(1) = 1
  • F(2) = 1
  • F(2i+1) = F(i)² + F(i+1)² for i > 0
  • F(2i) = F(i-1)F(i) + F(i)F(i+1) for i > 1
  In each of the four problems below, assume that an addition or a multiplication takes O(1) time, regardless of the size of the operands.
  1. Compute the asymptotic complexity of a simple recursive algorithm for computing F(n), making use of Definition 1.
  2. Compute the asymptotic complexity of a simple recursive algorithm for computing F(n), making use of Definition 2.
  3. Compute the asymptotic complexity of a dynamic programming algorithm for computing F(n), making use of Definition 1.
  4. Compute the asymptotic complexity of a dynamic programming algorithm for computing F(n), making use of Definition 2, where the algorithm uses memoization.
• Work exercise 16.3-5 on page 319 of your textbook.
• Work exercise 16.3-6 on page 319 of your textbook.
• Work exercise 17.2-4 on page 337 of your textbook.
• Challenge Problem.
  (Don't bother to contact the students who took the course in 1999. None of them were able to solve the Challenge Problem.)
  Good Luck.