MIT6006 Problem Set 7 Solution

Please write your solutions in the L ATEX and Python templates provided. Aim for concise solutions; convoluted and obtuse descriptions might receive low marks, even when they are correct.

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 to the original problem from the subproblems, and analyze running time. Correct but inefficient dynamic programs will be awarded significant partial credit.
Problem 7-1. [15 points] Effective Campaigning
Representative Zena Torr is facing off against Senator Kong Grossman in a heated presidential primary: a sequence of n head-to-head state contests, one per day for n days. Each state contest i ∈ {1,...,n} has a known positive integer delegate count di, and a projected delegate count zi < di that Rep. Torr would win if she took no further action. There are D = Pi di total delegates and Rep. Torr needs at least bD/2c +1 delegates to win. Unfortunately, Rep. Torr is projected to

lose the race, since Pi zi < bD/2c +1, so she needs to take action. Rep. Torr has a limited but effective election team which can campaign in at most one state per day. If the team campaigns on day i, they will win all di delegates in state i, but they will not be able to campaign at all for two days after day i, as it will take time to relocate. Describe an O(n)-time algorithm to determine whether it is possible for Rep. Torr to win the primary contest by campaigning effectively.
Problem 7-2. [15 points] Caged Cats
Ting Kiger is an eccentric personality who owns n pet tigers and n2 cages.
• Each tiger i has known positive integer age ai and size si (no two have the same age or size).
• Each cage j has known positive integer capacity cj and distance dj from Ting’s bedroom (no two have the same capacity or distance).
Ting needs to assign each tiger its own cage.
Describe an O(n3)-time algorithm to assign tigers to cages that favors older tigers and minimizes the total discomfort experienced by the tigers.
2 Problem Set 7
Problem 7-3. [15 points] Odd Paths
Problem 7-4. [15 points] Pizza Partitioning
Liza Pover and her little brother Lie Pover want to share a round pizza pie that has been cut into
2n equal sector slices along rays from the center at angles αi = iπ/n for i ∈{0, 1,..., 2n}, where α0 = α2n. Each slice i between angles αi and αi+1 has a known integer tastiness ti (which might be negative). To be “fair” to her little brother, Liza decides to eat slices in the following way:
• They will each take turns choosing slices of pizza to eat: Liza starts as the chooser.
• If there is only one slice remaining, the chooser eats that slice, and eating stops.
• Otherwise the chooser does the following:
– Angle αi is proper if there is at least one uneaten slice on either side of the line passing through the center of the pizza at angle αi.
– The chooser picks any number i ∈ {1,..., 2n} where αi is proper, and eats all uneaten slices counter-clockwise around the pizza from angle αi to angle αi + π.
– Once the chooser has eaten, the other sibling becomes the chooser, and eating continues.
Liza wants to maximize the total tastiness of slices she will eat. Describe an O(n3)-time algorithm to find the maximum total tastiness Liza can guarantee herself via this selection process.

Problem Set 7 3
Problem 7-5. [40 points] Shorting Stocks
Bordan Jelfort is a short seller at a financial trading firm. He has collected stock price information from s different companies C = (c0,...,cs−1) for n consecutive days. Stock price information for a company ci is a chronological sequence Pi = (p0,...,pnk−1) of nk prices, where each price is a positive integer and prices {pkj ,...,pkj+k−1} all occur on day j for j ∈ {0,...,n − 1}. The shorting value of a company is the length of the longest chronological subsequence of strictly decreasing prices for that company that doesn’t skip days: if the sequence contains two prices on different days i and j with i < j, then the sequence must also contain at least one price from every day in {i, . . . , j}.
(a) [15 points] Describe an O(snk2)-time algorithm to determine which company ci has the highest shorting value, and return a longest subsequence S of decreasing subse- quences of prices from Pi that doesn’t skip days.
(b) [25 points] Write a Python function short company(C, P, n, k) that imple- ments your algorithm from part (a) using the template code provided. You can down- load the code template and some test cases from the website.
1 def short_company(C, P, n, k):
2 ’’’
3 Input: C | Tuple of s = |C| strings representing names of companies
4 P | Tuple of s lists each of size nk representing prices
5 n | Number of days of price information
6 k | Number of prices in one day
7 Output: c | Name of a company with highest shorting value
8 S | List containing a longest subsequence of
9 | decreasing prices from c that doesn’t skip days
10 ’’’
11 c = C[0]
12 S = []
13 ##################
14 # YOUR CODE HERE #
15 ################## 16 return (c, S)
MIT OpenCourseWare
https://ocw.mit.edu
For information about citing these materials or our Terms of Use, visit: https://ocw.mit.edu/terms