Assignment #5 CMPUT 204

Assignment #5
(Total 40 marks)
CMPUT 204
A number of questions in this assignment are based on some problems and their solutions given in
Problem Set #4. If a problem is related to some exercises of CLRS, possible solutions may also be found
online. You may consult, adopt, or revise any of these solutions for your answers. If your algorithm is the
same as the one given in the Problem Set, just indicate so; otherwise please specify.
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