# 算法代写 | CSCI-GA.1170-001/002 Fundamental Algorithms

这个作业是根据具体场景设计算法策略

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

strategy:

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

books.

(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