Homework 23
due Mon 4/15 in class

For each of the following, develop an efficient dynamic programming algorithm using the 16-step dynamic programming development process discussed in class.

1. You are participating in a contest which consists of a series of challenges. The wrinkle is that completing a challenge takes time, and so doing challenge i will cause you to miss the next d_i challenges. (There's no way to go back to complete a missed challenge after the fact.) Given that you earn p_i points for completing challenge i (and that you complete any challenge you start), determine which challenges to do so as to maximize your score.

2. You have a paragraph consisting of n words that you wish to display on the screen. Word i is l_i characters long, and the display area is W characters wide. Since the text is most likely longer than the display area is wide, your task is to determine the best places to put in line breaks so that the text fits within the display area while also keeping the length of each line as even as possible and not using too many lines. This "niceness" criteria will be captured by assigning a cost of s³ to each line of text where s is the number of spaces at the end of the line. The goal is to determine where to put line breaks so as to minimize the total cost. Line breaks can only occur between words.