Computer Science 269
Introduction to Data Structures
Fall 2007
Assignment 5
Due Thursday, November 29, 2007.

-
Goals of this assignment:
-
To gain skill in the use of dynamic programming.
-
To appreciate the issue of time complexity.
-
To gain skill in documentation.
-
To learn the value of analyzing program efficiency before coding.
-
To appreciate the danger of "combinatorial explosion."
-
It is expected that students will discuss the assignments. But do
not turn in code written by another person. If that happens, both
persons are violating the ethics of this course. Representing the
work of another person as your own is plagiarism, and may result in
a disciplinary "F" in the course.
It is permissable (in this course, as this is up to the instructor)
for you to obtain ideas from other students or from other persons.
But you must type in the code yourself.
It is unadvisable for you to allow another student to have an electronic
copy of your work, as then you would unwittingly be a party to a breach
of these rules. Showing the other student a hard copy is less dangerous.
The above rule does not apply to copying files that I have made publicly
available. I expect that you will use those in their original form or
with appropriate modifications (made by just you, of course).
If you utilize code that you obtain from other sources, be sure to give
credit in a comment, such as:
// this code from website www.mit.edu/help/x13
-
Write an efficient program for computing a recursive function.
-
Consider the recursively defined function mystery. The
definition of this function is as follows:
-
mystery(n) is defined for any non-negative integer n.
-
If n<3 then mystery(n) = 1.
-
Otherwise, mystery(n) = mystery(n-3)*mystery(n-1)/mystery(n-2)+1.
For example, here are the first few values of the function:
-
mystery(0) = 1
-
mystery(1) = 1
-
mystery(2) = 1
-
mystery(3) = 2
-
mystery(4) = 3
-
mystery(5) = 2.5
Values of mystery(n) up to n=20
-
Write code to compute mystery in various ways:
-
Write a recursive function to compute mystery(n) for any
non-negative integer n. Hand in a hand-written paper
in which you prove that the time complexity of this function is
an exponential function of n, and thus impractical for
all but the smallest values of n. This hand-written paper
may not be the prinout of a computer file, and must be written by
your own hand, but can be supplemented by printouts from practice runs.
-
Write a program using dynamic programming which computes the value
of mystery(n) for any non-negative integer n which
the user inputs in O(n) time. Run this program for a variety
of values of n and document the time complexity.
-
Extra Difficulty Version.
Consider the recursively defined function secret. The
definition of this function is as follows:
-
Write three 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. Prove that this program takes O(n2)
time.
-
The second program should use dynamic programming in the ordinary manner,
and should take linear time, that is, O(n) time.
-
The third program must take
less than linear time.
It can actually be done in O(log n) time, although
I will be quite pleased if you can find anything that is asymptotically
faster than linear time.
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.
Documentation will be a requirement for this assignment:
-
A hand-written document, giving
showing that the recursive function takes
exponential time.
-
If you choose to do the extra-difficulty part of the assignment,
your document should also show that your algorithm takes less than
linear time.
-
Loop invariants, written as comments, for any tricky loop.
It is a judgment call whether a particular loop needs to
have its loop invariant written. Use the ``reasonable'' test.
Would a ``reasonably competent'' CSC major be helped, in understanding
your code, by seeing a comment explicitly stating this loop invariant?
-
Input and Output conditions for functions, again using the ``reasonable''
test.
-
Comments explaning variables and functions whose purpose is not obvious.
-
Other comments, as appropriate. But code that is overcommented looks
silly.
There are some students who want to write every conceivable comment,
"Just to be sure." Don't do that. I will instruct the grader to
take off points for ridiculous overcommenting. You are supposed to
use your judgment, and you are to be graded on how good your judgment
is.
As always, the programs must be executed on our system.
If you cannot get your program to run on our system, even though
it works on some other computer, that will be graded the same as
non-working code, in other words,
partial credit might be given.
Turn in all files, including a file that shows several sample runs.
All files must be turned in electronically to the teaching assisant.
The deadline for electronic submission is Thursday, November 29.
The submission must be timestamped before midnight.
Be sure to include the string "CS 302 001 Hw5" in the subject field
of your email.
