Introduction to Algorithms From S18 and F18

Massachusetts Institute of Technology 6.006 Fall 2018

Instructors: Zachary Abel, Erik Demaine, Jason Ku Solution: Quiz 3

Solution: Quiz 3
• Do not open this quiz booklet until directed to do so. Read all the instructions on this page.
• When the quiz begins, write your name on the top of every page of this quiz booklet.
• You have 60 minutes to earn a maximum of 60 points. Do not spend too much time on any
one problem. Skim them all first, and attack them in the order that allows you to make the
most progress.
• You are allowed three double-sided letter-sized sheet with your own notes. No calcula-
tors, cell phones, or other programmable or communication devices are permitted.
• Write your solutions in the space provided. Pages will be scanned and separated for grading.
If you need more space, write “Continued on S1” (or S2, S3) and continue your solution on
the referenced scratch page at the end of the exam.
• Do not waste time and paper rederiving facts that we have studied in lecture, recitation, or
problem sets. Simply cite them.
• When writing an algorithm, a clear description in English will suffice. Pseudo-code is not
required. Be sure to argue that your algorithm is correct, and analyze the asymptotic
running time of your algorithm. Even if your algorithm does not meet a requested bound,
you may receive partial credit for inefficient solutions that are correct.
• Pay close attention to the instructions for each problem. Depending on the problem,
partial credit may be awarded for incomplete answers.

Problem Parts Points

0: Information 2 2
1: Pseudo-Circling 3 3
2: Dealer’s Choice 1 17
3: Sweet Tapas 1 19
4: Gokemon Po 1 19
Total 60

Name:

School Email:
2 6.006 Solution: Quiz 3 Name

Problem 0. [2 points] Information (2 parts)

(a) [1 point] Write your name and email address on the cover page.
Solution: OK!

(b) [1 point] Write your name at the top of each page.

Solution: OK!
6.006 Solution: Quiz 3 Name 3

Problem 1. [3 points] Pseudo-Circling

Solve each of the following problems using dynamic programming. 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.
In addition, indicate whether the running times of each of the following problems are polynomial
or psuedo-polynomial by circling the appropriate word below. (1 point each)

(a) Problem 2: Dealer’s Choice Polynomial Pseudo-polynomial

Solution: Polynomial

(b) Problem 3: Sweet Tapas Polynomial Pseudo-polynomial

Solution: Pseudo-polynomial

(c) Problem 4: Gokemon Po Polynomial Pseudo-polynomial

Solution: Polynomial
4 6.006 Solution: Quiz 3 Name

Problem 2. [17 points] Dealer’s Choice

Annie Doeshun plays a card game against a single opponent using a deck of 2n cards, where each
card has a positive integer value. At the beginning of the game, Annie deals n cards to each player.
After the deal, Annie’s advantage will be the total value of cards dealt to her, minus the total
value of cards dealt to her opponent. Annie has some flexibility when dealing cards: she first deals
either one or two cards to her opponent from the top of the deck, immediately followed by dealing
the same number of cards to herself. She repeats this procedure (dealing both players either one
or two cards, opponent first) until all cards are evenly dealt. Given the values of the 2n cards in
their deck order at the start of the deal, describe an O(n)-time dynamic programming algorithm to
determine the largest advantage Annie can have at the end of the deal.
Solution:

1. Subproblems
• Let the card values be C1 , C2 , . . . , C2n from top to the bottom
• Let x(2i) be the maximum advantage possible after dealing a total of 2i cards from the
top of the deck, i to each player, in the specified manner
2. Relate
• Either Annie deals her opponent one card or two (Guess!)
• If she deals one, her opponent gets the next card, and she gets the one after
• If she deals two, her opponent gets the next two cards, and she gets the two after
• x(2i) = max{x(2i − 2) − C2i−1 + C2i , x(2i − 4) − (C2i−3 + C2i−2 ) + (C2i−1 + C2i )}
• Subproblems x(2i) only depend on strictly smaller i, so acyclic
3. Base
• x(0) = 0 (nothing dealt yet)
• x(2) = −C1 + C2 (two cards dealt)
4. Solution
• Solve subproblems x(2i) in order of increasing i for 2 ≤ i ≤ n
• Solution to problem is subproblem x(2n), maximizing the entire 2n-card deck
5. Time
• # Subproblems is n + 1
• Work per subproblem is O(1)
• Total running time is O(n)
6.006 Solution: Quiz 3 Name 5

Problem 3. [19 points] Sweet Tapas (1 part)

Obert Ratkins is having dinner at an upscale tapas bar, where he will order many small plates
which will comprise his meal. There are n plates of food on the menu, with each plate pi having
integer volume vi , integer calories ci , and may or may not be sweet. Obert is on a diet: he wants
to eat no more than k calories during his meal, but wants to fill his stomach as much as he can. He
also wants to order exactly s sweet plates, for some s ∈ {1, . . . , n}, without purchasing the same
dish twice. Describe an O(n2 k)-time dynamic programming algorithm to find a set of plates that
maximizes the volume of food Obert can eat given his constraints.
Solution:

1. Subproblems
• Let si be 1 if plate pi is sweet and 0 otherwise
• x(i, j, s0 ): largest volume of food orderable from plates pi to pn , using at most j calories,
ordering exactly s0 sweet plates
2. Relate
• Either we order plate pi or not. Guess!
• If order pi , get vi in volume but use ci calories
• If pi is sweet, need to order one fewer sweet plate
vi + x(i + 1, j − ci , s0 − si )) if ci ≤ j and si ≤ s0

0
• x(i, j, s ) = max
x(i + 1, j, s0 ) always
0
• Subproblems x(i, j, s ) only depend on strictly larger i so acyclic
3. Base
• For all j ∈ {0, . . . , k}: x(n + 1, j, 0) = 0 and x(n + 1, j, s0 ) = −∞ for s0 6= 0
4. Solution
• Solve in order of decreasing i, then j and s0 in any order
• Solution to problem is subproblem x(1, k, s)
5. Time
• (# Subproblems) × (work per problem) = O(nsk) × O(1) = O(nsk) = O(n2 k)
6 6.006 Solution: Quiz 3 Name

Problem 4. [19 points] Gokemon Po (1 part)

Kash Etchum wants to play a new augmented reality game, Gokemon Po, where the goal is to catch
a set of n monsters M = {m1 , . . . , mn } who reside at specific locations in her town. Monsters
must be caught in a specified linear order: Kash can catch monster mi only after she has already
caught monster mj for every j ∈ {1, . . . , i − 1}. To catch monster mi , Kash may either purchase
the monster in-game for ci dollars, or she may catch mi for free from that monster’s location. If
Kash is not at the monster’s location, she will have to pay a ride share service to drive her there.
The minimum possible cost of transporting from monster mi to monster mj via ride sharing is
denoted s(i, j). Given a list of prices of in-game purchases and ride sharing trips between all
pairs of monsters, describe an O(n2 ) dynamic programming algorithm to determine the minimum
amount of money Kash must spend in order to catch all n monsters, assuming that she starts at the
location of monster m1 .
Solution:

1. Subproblems
• x(i, j): min cost of catching monsters mi to mn starting at location mj for j ≤ i
2. Relate
• Either acquire monster mi by purchasing or ride-sharing to location. Guess!
• If purchase spend ci dollars, else need to ride share to mi from mj

min(ci + x(i + 1, j), s(j, i) + x(i, i)) if j < i
• x(i, j) =
x(i + 1, j) if j = i
• Subproblems x(i, j) only depend on strictly larger i + j so acyclic
3. Base
• x(n + 1, j) = 0 for j ∈ [1, n]
4. Solution
• Solve in order of decreasing i, then decreasing j
• Solution given by x(1, 1)
5. Time
• (# Subproblems) × (work per problem) = O(n2 ) × O(1) = O(n2 )
6.006 Solution: Quiz 3 Name 7

SCRATCH PAPER 1. DO NOT REMOVE FROM THE EXAM.

You can use this paper to write a longer solution if you run out of space, but be sure to write
“Continued on S1” on the problem statement’s page.
8 6.006 Solution: Quiz 3 Name

SCRATCH PAPER 2. DO NOT REMOVE FROM THE EXAM.

You can use this paper to write a longer solution if you run out of space, but be sure to write
“Continued on S2” on the problem statement’s page.
6.006 Solution: Quiz 3 Name 9

SCRATCH PAPER 3. DO NOT REMOVE FROM THE EXAM.

You can use this paper to write a longer solution if you run out of space, but be sure to write
“Continued on S3” on the problem statement’s page.
10 6.006 Solution: Quiz 3 Name

SCRATCH PAPER 4. DO NOT REMOVE FROM THE EXAM.

You can use this paper to write a longer solution if you run out of space, but be sure to write
“Continued on S4” on the problem statement’s page.