MIT6006 Problem Set 8 Solution

Please write your solutions in the L ATEX template provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct. There is no coding part to submit.

Please solve each of the following problems using dynamic programming. For each problem, be sure to define a set of subproblems, relate the subproblems recursively, argue the relation is acyclic, provide base cases, construct a solution from the subproblems, and analyze running time. Correct but inefficient dynamic programs will be awarded significant partial credit.

For each problem below, please indicate whether the requested running time is either:
(1) polynomial, (2) pseudopolynomial, or (3) exponential in the size of the input. This categorization will be worth 3 points per problem.

Problem 8-1. [25 points] Oil Well that Ends Well
Problem 8-2. [25 points] Splits Bowling
In Lecture 15, we introduced Bowling: a one-player game played on a sequence of n pins, where pin i has integer value vi (possibly negative). The player repeatedly knocks down pins in two ways:
• knock down a single pin, providing vi points; or
• knock down two adjacent pins i and i +1, providing vi · vi+1 points.
• knock down two pins i and j > i + 1 if all pins in {i + 1,...,j − 1} between them have already been previously knocked down, providing vi · vj points.
Describe an O(n3)-time algorithm to determine the maximum score possible playing Split Bowling on a given input sequence of n pins.
2 Problem Set 8
Problem 8-3. [25 points] Quarter Partition

Given a set A = {a0,...,an−1} containing n distinct positive integers where m = Pai∈A ai, describe an O(m3n)-time algorithm to return a partition of A into four subsets A1,A2,A3,A4 ( A
(where A1 ∪ A2 ∪ A3 ∪ A4 = A ) such that the maximum of their individual sums is as small aso
n possible, i.e., such that max Pai∈Aj ai | j ∈ {1, 2, 3, 4} is minimized.
Problem 8-4. [25 points] Corrupt Chronicles
Kimmy Jerk is the captain of the USS Exitcost, a starship charged with exploring new worlds. Each day, Capt. Jerk uploads a captain’s log to the ship’s computer: a string of at most m lowercase English letters and spaces, where a word in a log is any maximal substring not containing a space.
One day, Capt. Jerk is abducted, and Communications Officer Uhota Nyura goes to the captain’s logs looking for evidence. Unfortunately, the log upload system has malfunctioned, and has corrupted each of the last n logs by dropping all spaces. Officer Nyura wants to restore the spaces based on Capt. Jerk’s speech patterns in previous logs. Given a list Lc of the n corrupted logs, as well as a list Lu of O(m2n) uncorrupted logs from before the malfunction, Officer Nyura wants to:
• for each word w appearing in any log in Lu, compute f(w): the positive integer number of times word w appears in Lu (note, f(w) is zero for any word w not appearing in Lu); and
• for each log `i ∈ Lc, return a restoration Ri of `i (i.e, a sequence of words Ri whose ordered concatenation equals ` i), such that Pw∈Ri f(w) is maximized over all possible restorations.
Describe an O(m3n)-time algorithm to restore Capt. Jerk’s logs based on the above protocol.
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms