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:
-
secret(n) is defined for any non-negative integer n.
In this definition, "/" denotes truncated division; for example,
5/2 denotes 2.
-
If n<2 then secret(n) = 0.
-
Otherwise,
secret(n)=secret(n/2)*secret((n+1)/2)+
secret((n-1)/2)*secret((n-2)/2)+1
-
Values for n up to 40.
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.
The first program must be recursive, simply mocking the recursive definition
of the function. This program takes O(n2)
time. (Can you prove that?)
The second program should use dynamic programming in the ordinary manner,
and should take linear time, that is, O(n) time.
The third program, for Extra Credit must take
less than linear time.
It can be done in O(log n log log n) time using
memoization, but
I will be quite pleased if you can find anything that is asymptotically
faster than linear time.
Wikipedia entry.
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.
