Extra Credit 1

The same rules apply here as for the take-home exam. You should not obtain help from anybody or anything, except your instructor, your written class notes, the textbook (Dasgupta, Papadimitriou, & Vazirani, available on paper or on-line), and the course Web site.

This assignment, worth 15 points, is due at 2pm, Wednesday, March 18. You should submit your solution on paper, either handwritten or typed. E-mailed solutions will not be accepted.

Suppose we have a rectangular sheet of paper that is W inches wide and H inches tall. We are interested in cutting out rectangles of particular sizes from this paper; there are n such rectangular templates, each with dimensions a_i × b_i inches for i between 1 and n (inclusive). We would like pack the paper with these templates so as to leave as little of the paper unused as possible, even if this means having no instances of some templates. Since the paper is striped, we need to make sure that rectangle i is cut with a_i in the horizontal dimension (like W) and b_i in the vertical dimension (like H). All dimensions are integer numbers of inches.

However, the only way we have for cutting the paper is a a paper cutter, which cuts through the whole dimension we feed into it. Thus, if I cut vertically a inches down from the left side of the paper, that leaves me with one strip a inches wide and another w − a inches wide, both the same height.

For example, suppose we have a sheet of paper that is 11 inches wide and 9 inches tall. The choices of templates are 3×8, 4×6, 5×7, 6×4, and 7×5. The best choice is to cut vertically once, leaving a 6-inch-wide strip and a 5-inch wide strip both 9 inches tall. We'd cut the 6-inch-wide strip into two 6×4 templates, and we'd cut the 5-inch-wide strip into one 5×7 template. This leaves 16 square inches of unused paper.

Using dynamic programming, design an O(W H n)-time algorithm to compute the amount of unused paper. (Your algorithm doesn't have to compute how that amount is actually achieved.) Argue that your program works and takes the required amount of time.