Due Date: December 13th, 2005 at 2:00 PM
See course policy regarding late homework submissions
- Read Chapter 6 of the textbook in detail.
- Problems: You need to turn in a hard copy of your written
solutions to the following exercises
at the beginning of class on the day the homework is due.
Remember to show your work and explain your answers.
Correct answers without complete explanations won't receive full credit.
Incorrect answers with explanations may receive partial credit.
- (50 points + 15 extra credit points) Chapter 6: exercise 5.
Remember to:
- (25 points) Provide a detailed description of the
DYNAMIC PROGRAMMING idea underlying your algorithm design,
and elaborate on why these algorithmic idea is correct
(i.e., it solves the problem).
- (25 points) Provide a detailed algorithm to
solve this problem based on your ideas above.
- (15 extra points) State and prove rigorously what
the tighest upper bound of the runtime of your algorithm is.
- (50 points)Chapter 6: exercise 7.
(Read Chapter's 5 Solved exercise 2 on pp. 244-246 to better understand the
problem.)
Remember to:
- (17 points) Provide a detailed description of the
DYNAMIC PROGRAMMING idea underlying your algorithm design,
and elaborate on why these algorithmic idea is correct
(i.e., it solves the problem).
- (17 points) Provide a detailed algorithm to
solve this problem based on your ideas above.
- (16 points) Prove rigorously that your algorithm runs in O(n).