CSCI-GA.1170-001/002 Fundamental Algorithms April 8, 2020
Problem Set 9
Lecturer: Yevgeniy Dodis Due: 8 pm on Thursday April, 16
Problem 9-1 (Gotta Catch ’Em All) (19 points)
In the time of quarantine you have gone back to your roots playing the game of Pokemon, only this
is a weirder version of the original game. You are a Pokemon trainer battling Team Rocket and you
use your Pikachu to fight against their Arbok. You manage to win with a residual HP of u units
but your Pikachu is poisoned. This means that your Pikachu is going to lose its HP by 1 unit every
r miles. You start at mile marker s0 in this situation and you need to go to a Pokemon Center
which accepts Pokeaid, the Kanto government’s public health insurance. This is located at sn mile
marker. You are not sure if you can make it without killing your Pikachu but you are told that
there exists a Pokemon Clinic at mile markers s0, . . . , sn−1. However, these do not accept Pokeaid
and comes with a high co-pay to use. You also know that the max HP of your Pikachu is c. As is
typical, the Pokemon Center is the only one with the antidote and the clinics can only restore the
HP and not cure the poisoning. Therefore, you want to get to the Pokemon Center while ensuring
that the HP of your Pikachu can go neither below 0 nor above c.
The variables at a glance:
• u: Initial HP of Pikachu
• s0: Start position
• sn: Destination location.
• s0, . . . , sn: Mile Markers
• c: Max HP of Pikachu
• r: Number of miles you may travel before the Pikachu loses 1 HP.
• Constraint: Pikachu’s HP can neither go below 0 nor above c.
(a) (6 points) Given the exorbitant co-pay at every clinic, you want to minimize the number of
stops you make while meeting the constraint. You come up with the following strategy:
Do this until at destination:
• Restore HP fully at current clinic.
• Travel to the farthest clinic you can on the full HP.
Prove that this strategy results in minimum number of stops at a clinic. Note that there is a
clinic at the initial point. Use an exchange argument to prove the correctness. (Hint: Let the
input I be u, s0, s1, . . . , sn, c, r. You will use induction on size of input, specifically n. Let Z
be any strategy acting on input I. Let G be the greedy strategy. You will modify the strategy
Z into a strategy Y which is similar to the greedy strategy G and then use induction.)
PS 9, Page 1
As you are about to set off on your journey you hear a shocking update. The greedy Pokemon
Clinics have decided to make more money by charging a cost for every HP unit restored. You are
given this as an array pi for i = 0, …, n −1 where pi
is the cost levied per HP unit restored at point
i. Assume pn = 0.
(b) (3 points) Your rival, Gary Oak, sends you a message with the following strategy:
Do until at destination
• If you could reach a cheaper clinic, on a full HP, then restore the minimum amount of
HP needed, which could possibly be 0, to reach the cheapest such clinic and go there.
• Otherwise, restore HP fully to get to the next clinic.
You are skeptical about Gary’s sudden desire to help you. Prove that Gary’s strategy is not
optimal by constructing a counter example.
(c) (10 points) You turn to the wise man, Professor Oak, for advice. He provides the following
Do until at destination
(i) If you could reach a cheaper clinic, on a full HP, then restore the minimum amount of
HP needed, which could possibly be 0, to reach the first such clinic and go there.
(ii) Otherwise, restore HP fully to get to the next clinic.
Prove that this strategy is optimal by an exchange argument. (Hint: Let the input I be
u, s0, s1, . . . , sn, p1, . . . , pn, c, r. Let G be the greedy strategy and Z be any strategy on the
input. You will again use induction on n. Let Z be any strategy on input I and let G be the
greedy strategy. You will have to show that Z is no better than G. Unlike part (a) you will
need to transform it into two different strategies based on the two cases in the greedy algorithm
– (i) and (ii). Specifically, you need to transform Z into Y1 such that Cost(Z) ≥ Cost(Y1)
and where Y1 lines up with G under case (i) of G. You will also need to transform Z into
Y2 such that Cost(Z) ≥ Cost(Y2) and where Y2 lines up with G under case (ii) of G. Once
again do not forget to show that all of the inputs are same for the induction part.)
Problem 9-2 (Arranging Books on Book Shelves) 13 Points
Consider the problem of storing n books on shelves in a library. The order of the books is fixed
by the cataloging system and so cannot be rearranged. The i-th book bi
, where 1 ≤ i ≤ n has a
thickness ti and height hi stored in arrays t[1 . . . n] and h[1 . . . n]. The length of each bookshelf at
this library is L. We want to minimize the sum of heights of the shelves needed to arrange these
(a) (5 points) Suppose all the books have the same height h (i.e., h = hi for all i) and the shelves
are each of height h, so any book fits on any shelf. The greedy algorithm would fill the first
shelf with as many books as we can until we get the smallest i such that bi does not fit, and
then repeat with subsequent shelves. Show that the greedy algorithm always finds the shelf
placement with the smallest total height of shelves, and analyze its time complexity. You will
prove this using the Greedy Always Stays Ahead (GASA) proof technique.
PS 9, Page 2
(b) (2 points) Now assume that the books are not of the same height, and hence the height of any
shelf is set to be the height of the largest book placed on that shelf. Show that the greedy
algorithm in part (a) doesn’t work for this problem by giving a counter example.
(c) (6 points) Give an alternative dynamic programming algorithm to solve the problem mentioned in part (c). Present a recursive formula, argue its correctness and write a pseudocode
to implement the same. What is the running time of your algorithm?
Problem 9-3 (Greedy Matrix Multiplication) 10 points
Recall the dynamic programming solution for the matrix chain multiplication problem. Here we
give two greedy candidate solutions for this problem. For each of the proposed solutions find a
counter-example proving that it is not correct.
(a) (5 points) In each step we will ”get rid” of the biggest possible dimension pi (intuitively, we
want to ”pay” for such huge pi only once). Formally, let pi be the biggest value of dimension:
i.e., the matrix Ai has dimension pi−1×pi and the matrix Ai+1 has dimension pi×pi+1, where
pj ≤ pi for all j. Then we will multiply Ai with Ai+1 first. After that we repeat the same
greedy procedure on the remaining n − 1 matrices. And so on until we get the final result.
(b) (5 points) In each step choose such a pair of adjacent matrices Ai and Ai+1 such that the cost
of multiplication them is the smallest possible at this point. Namely, pi−1pipi+1 ≤ pj−1pjpj+1,
for all j. Then multiply Ai and ai+1 first. After that we repeat the same greedy procedure
on the remaining n − 1 matrices. And so on until we get the final result.
PS 9, Page 3
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx