## Description

Problem 1. (9 marks) Consider the following problem from Problem Set #4:

A native Australian named Oomaca wishes to cross a desert carrying only a single water bottle. He

has a map that marks all the watering holes along the way. Assuming he can walk k miles on one bottle

of water, design an efficient algorithm for determining where Oomaca should refill his bottle in order to

make as few stops possible. Argue why your algorithm is correct.

You are asked to answer the following questions.

What is the greedy choice in your algorithm?

Assume Oomaca starts with a full bottle of water and can walk 1 mile on one bottle of water. Suppose

watering holes are located at the points given in the following list

H = {0.5, 1.2, 1.4, 1.8, 1.9, 2.2, 3.1, 3.5, 4.1, 4.5, 4.7, 5.0, 6.0}

measured in terms of miles from the starting point, where 6.0 also denotes the end point of the desert

being crossed. Show all the location points where Oomaca refills his bottle by your algorithm.

Given a problem instance, suppose S = {q1, q2, . . . , qn} is an optimal solution where each qi

is a

location point to refill the bottle. Further assume S is sorted in ascending order, thus q1 is the first

point for a refill in S. Show that there is an optimal solution that contains your first point of refill.

(Hint: This is to show that your first point of refill can be substituted into any optimal solution

resulting in an optimal solution. Do not write a full proof – you are not asked to do that.)

Problem 2. (9 marks)

Consider the following question from Problem Set #4:

Describe an efficient greedy algorithm for making change for a specified value using a minimum

number of coins, assuming there are four denominations of coins (called quarters, dimes, nickels,

and pennies), with values 25, 10, 5, and 1, respectively. Argue why your algorithm is correct

In this assignment, you are asked to answer the following questions.

Assume the change to be made is 98 cents. Show the solution generated by your algorithm.

Given a problem instance, suppose S = {q25, q10, q5, q1} is the solution generated by your algorithm,

where qi

is the number of coins in denomination i. Argue why your solution is optimal.

(Hint: Start by assuming S

0 = {q

0

25, q0

10, q0

5

, q0

1

} is an optimal solution and show that your greedy

choices can be substituted into this optimal solution resulting in an optimal solution. In this question,

you first argue why S

0 = {q25, q0

10, q0

5

, q0

1

} is an optimal solution, and then apply the same argument

to the rest of greedy choices. )

1

Give an example set of denominations of coins so that a greedy change making algorithm will not

use the minimum number of coins. Your answer must include denomination 0.01 so that a solution

is always guaranteed, and must also be different from the one given in Problem Set #4, where the

denominations are 0.25, 0.24, 0.01.

Problem 3. (9 marks) Consider the following problem from Problem Set #4:

In the art gallery guarding problem, a line L represents a long art gallery hallway. We are

given a set of location points on it X = {x0, x1, . . . , xn−1} of real numbers that specify the

positions of the paintings along the hallway. A single guard can guard paintings standing at

most 1 meter from each painting on either side. Propose an algorithm that finds the optimal

number of guards to guard all the paintings along the hallway.

In this assignment, you are asked to answer the following questions.

Given the set of location points

X = {0.1, 0.5, 1.2, 1.8, 2.3, 3.1, 4.5, 6.7, 7.5}

that specify the positions of the paintings along the hallway (measured in meters from the beginning

of the gallery hallway), show all the position points at which your algorithm places a guard.

Argue that, for any given problem instance, there is an optimal solution that places the first guard

at the same position point as your algorithm does.

(Hint: This is to show that, given any problem instance, the placement of your first guard, say at

q1, can always be substituted into any optimal solution resulting in an optimal solution. Start your

argument by assuming an optimal solution S = {p1, p2, . . . , pk}. Do not write a full proof.)

Problem 4. (13 marks) A server has n customers waiting to be served. The service time required by each

customer is known in advance: it is ti minutes for customer i. So if, for example, the customers are served

in order of increasing i, then the ith customer has to wait Pi−1

j=0 tj minutes, where 1 ≤ i ≤ n and t0 = 0.

We wish to minimize the total waiting time

T =

Xn

i=1

(time spent waiting by customer i)

Give an efficient algorithm for computing the optimal order in which to process the customers. Prove that

your algorithm gives an optimal solution.

Hint: Denote the problem input by A = [t0, t1, t2, . . . , tn]. We sort A in ascending order to obtain

B = [tπ0

, tπ1

, . . . , tπn

], such that tπ0 ≤ tπ1 ≤ · · · ≤ tπn

, where πis are the new indices after sorting.

Construct your algorithm based on this ordering and show it gives an optimal solution.

2