CS 223 In-lab 6
Week of 3/6

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Greedy Algorithms

Do Exercise 16.2-4 in the CLRS book.  Don't worry about the proof part, just come up with a greedy algorithm to solve the problem.  You may assume that the professor's tank is full at the start of the journey (there is gas station next to his house and fills up before leaving).  Hint: Draw a line with points at each gas station.  Consider how far he can drive if he fills up an each station, then select the optimal set of stations to fill at.

Turn you your algorithm into a simple program that takes the following input:

<car's range> (integer)
<distance to final destination>
<# of gas stations>
<gas station 1 location> (integers)
<gas station 2 location>
<gas station 3 location>
...

Sample file:
100
700
15
25
75
90
135
200
225
270
320
360
400
410
500
550
585
605

As output, you program should produce the list of optimal gas station locations that the professor should fill up at.

What to Turn In

• Source code and two sample runs (the above and one of your own creation).