Computer Science

York University EECS 3101 July 24, 2018

Homework Assignment #6A Due: July 31, 2018 at 7:00 p.m.

1. Jim Morton wants to start up a chain of doughnut shops. He wants to find the best way to locate the shops along Highway 401 from Windsor to Bainsville, Ontario. There are n towns along the highway. Shops can only be built in the towns (not between them). However, Jim only has enough capital to build k shops, where k < n. He would like to choose k of the n possible towns to minimize the average distance a person who lives in any of the towns along the highway has to drive to get to the nearest shop.

The towns are numbered 1..n from west to east. The distance from Windsor to town i is di kilometres, where 0 = d1 < d2 < d3 < · · · < dn. The population of town i is pi. Assume the towns are small so that the distance someone who lives in town i has to travel to get to the Jim Morton’s shop in town j is exactly |dj −di| kilometres.

Thus, if the nearest shop to town i is in town ji, the average distance to the nearest shop is

AV G =

n∑ i=1

pi · |di −dji| n∑

i=1

pi

.

Let A[x, y] be the minimum possible value of n∑

i=x

pi ·|di−dji| if at most y shops are placed

in towns x..n AND one of those y shops is in town x. Jim does a little precomputing of some arrays in O(n) time of some values he thinks

might be useful:

P [0] = p0

P [i] = P [i− 1] + pi for 1 ≤ i ≤ n PD[0] = 0

PD[i] = PD[i− 1] + pi ·di

(a) What are the ranges of possible values for x and y in the definition of A?

(b) Describe how to compute the entries of A efficiently. You can do this by simply giving a recurrence relation (including base cases). Explain why your answer is correct.

(c) Describe the order in which you would compute entries of the array using the recurrence relation.

(d) How can you obtain the best value of AVG from your array.

(e) Give a bound on the running time of the dynamic programming algorithm described in (a). Use big-Θ notation to state the bound in terms of n and/or k. Assume that arithmetic operations can be done in O(1) time. Explain why your answer is correct.

1