What to submit and when:
Work in pairs.
The goal of the lab is to get practice with dynamic programming.
Problem 15-9 p. 410 in CLRS:
A certain string processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. There is no operation that allows you to break a string into more than two pieces at once. For instance, breaking a string into three pieces requires breaking it into two pieces twice (with the corresponding copying). Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example suppose we wish to break a 20 character string after characters 2,8, and 10:
Your task is to develop and implement a dynamic programmming solution. Your first effort should be on working with examples and trying to identify subproblems to solve and the overlaps between them. Write them down as a part of your documentation.
Next, identify a bottom-up strategy: solving the simple subproblems first, and then building solutions for more complex ones based on those. Rewrite your example as a sequence of solutions in a bottom-up manner.
Write a program that reads the length of a string, the nubmer of positions to break it at and the actual positions (for instance, breaking a string of length 5 at positions 2 and 4 means that it is broken into segments of length 2, 2, and 1 left to right), and outputs all of the subproblems it is solving (with their solutions) and the solution for the problem itself. Each subproblem consitist of the length of a string, the positions at which it is broken (or, alternatively, the lengths of pieces left to right), the total cost, and the sequence that makes up the cost.
Try your solution on a string of length 30 that you want to break at positions 2, 5, 8, 11, and 17.
What is the run time efficiency of your approach to copying (in the number of character copying steps)? Please explain. Note that this question is different from asking what the efficiency of your program is since you are not doing the copying.
The minimum requirements include a clear description of the algorithm in the program and a worked out test example (with expected values) on paper (or a picture of a white board).
Extra credit (in lab groups): a complete implementation, either as a dynamic programming approach or as memoization.
Extra extra credit (individual or in pairs, submitted at any point before the final): explain why there is no greedy solution strategy for the problem. This is somewhat informal (it's very difficult to prove that there is no such strategy), but you can come up with a reasonable proposal for a greedy strategy that works for the above example, and then give an example that breaks it.
Submit your examples (written ok), your program (if you have one) and the documentation (as comments or as a separate file).