Lab 1
Messing with Greedy Algorithms
Due at end of lab, 9/22
Program due 9/24, end of day
The lab purpose is to develop several greedy algorithms and prove that they are correct.
1. Gas Station Planning
You are driving a car with a range of R miles per tank of gas. You must travel M miles total from origin to destination. Along your trip, there are gas stations at various distances from your origin. Plan gas stops so that you do not run out of gas (running out just as you pull into a staion is OK), and so that you stop as few times as possible.
Example: You get 400 miles on a tank, and must travel 2400 miles (R = 400; M = 2400) Stations are at:
300, 350, 400, 500, 750, 790, 810, 900, 950, 1100, 1150, 1180, 1210, 1300, 1450, 1550, 1771, 1801, 1901, 2250
Develop two different greedy algorithms for this problem, each arriving at different solutions for the case above.
2. Schedule planning
You must staff a help desk so that at least one person is available for a given time period from T1 to T2 (times are all integers). Staff members are available to work at time intervals given. You must schedule them for the time interval they have available, nor more and no less, but you may pick which people you schedule. Choose a set of staff members so that at least one is always on duty, and you choose as few members as possible.
Example: Must staff from time 10 to time 100
Staff availability (start, end):
Person 1: (5, 15)
Person 2: (3, 16)
Person 3: (10, 14)
Person 4: (8, 11)
Person 5: (9, 15)
.....
I have not shown all staff availability, in part to prevent you from looking to closely at the concrete example itself. Create a greedy algorithm to solve this problem, and a proof that it is correct.
General Greedy Proof Structure
i. Describe exactly the single, greedy, choice you make at each step. Do not describe the full algorithm. Just the greedy choice.
ii. Postulate an alternate solution A, supposedly better than one that starts with your greedy choice from above, but do not tie it specifically to any sample data. You may mention some concrete data as an example, but it must be clear from your argument that the logic will apply for any data set.
iii. Demonstrate that the alternate solution can be adjusted, by a simple substitution, into a solution B at least as good as A, where B starts with your greedy choice. Provide a clear explanation of why the alternate is at least as good; do not simply state that it is.
iv. Show that after making an initial greedy choice, you are left with a remaining problem that is a smaller version of the starting problem, so that repeated application of the greedy rule is appropriate.
3. Turn in on paper (yes, paper) to me:
a. A description both of your algorithms for problem 1, along with the solutions they provide.
b. A proof of their correctness, following the form above.
c. Show convincingly that this statement is wrong:
I made a 2000 mile trip, with a 300 mi tank-range. Gas stations were available at mile markers 1725, 1750, and 1875. There were also a number of stations available at mile markers prior to 1725. I was able to stop fewer times than any other possible schedule, but to do it I had to make my last stop at the 1750 mile marker station.
d. A description of your solution for problem 2 above.
e. A proof of correctness for your problem 2 solution.
4. After your paper submit (not approval):
Write a Java class GreedyScheduler.java, which implements the Scheduler interface you may find in my Vogon directory ~grade_cstaley/349/Scheduler in the source file Scheduler.java. Put your class in the same package as my interface. There is also a GreedyScheduler.class file providing my implementation (You'll need to stick in in the appropriate directory tree in your account in order to use it.
Create a test main for your class that exercises it with test cases of up to 1000000 staff members and runs efficiently. Submit your solution as GreedyScheduler.java to the turnin directory ~grade_cstaley/349/Scheduler/turnin, following the rules in Bender and Turnin.
Standard error codes for paper submit. Check that you have not made any of these errors, before submitting:
I’ll use these standard error numbers, since they are very common.
For part a.
E1. Your second algorithm isn’t correct, though the first one is.
For part b.
E2. You didn't do step 1 correctly
E3. You didn't do step 2 correctly. Perhaps you didn't describe your alternate solution carefully enough.
E4. You didn't do step 3 correctly.
E5. You tied your proof too specifically to concrete data, and did not leave it general.
E8. You simply stated that substitution with a greedy choice was just as good, but did not convince me of this. My response is to your substitution is “Yeah, but you'll mess up all your other station choices by changing that one, so how can you be sure it's just as good.” You need something that clearly answers that objection.
For part c:
E6. You need to make a more convincing argument, drawing on the proofs you did in part b.
For
part .d
E7. Your algorithm isn’t correct.
For part b.
E8. You didn't do step 1 correctly
E9. You didn't do step 2 correctly. Perhaps you didn't describe your alternate solution carefully enough.
E10. You didn't do step 3 correctly.
E11. You tied your proof too specifically to concrete data, and did not leave it general.
E12. You simply stated that substitution with a greedy choice was just as good, but did not convince me of this.