## CSci 3501 Algorithms and Computability - Lab 12.

#### Extra credit may be submitted any time before the final

What to submit and when:

• All submissions are electronic: by e-mail to and CC to all lab partners. Please do not delete your e-mail from "Sent mail" or your mailbox until the end of the semester.
• When working on the lab, please comment your work so that it is clear what contributions of each person are.
• At the end of the lab each group should send me the results of their in-class work. Please indicate if this is your final submission.
• If your submission at the end of the lab time was not final, please send me(CC to the lab partner(s)) a final copy before the due time. Please use the subject "3501 Lab N", where N is the lab number.

### Lab assignment

Work in pairs.

#### Lab overview and goals

The goal of the lab is to get practice with dynamic programming.

#### Dynamic programming (20 points)

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:

• If the breaks are made in left-right order, then the ﬁrst break costs 20 units of time, the second break costs 18 units of time and the third break costs 12 units of time, a total of 50 steps.
• If the breaks are made in right-left order, the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of only 38 steps.

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).

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.