Computer Science 269
Introduction to Data Structures
Fall 2012
Assignment 6: Dynamic Programming

Due Tuesday, November 13, 2012.

Consider the recursively defined function secret. The definition of this function is as follows:
  • Write two (or three for extra credit) programs, each of which computes the value of secret(n) for any non-negative integer n which the user inputs. Be sure to document the time complexity of your algorithm with a hand-written paper, perhaps supplemented by printouts from practice runs.
    The "usual" dynamic programming approach works by computing secret(i) for all i from 0 to n. which means that it cannot possibly take less than linear time.