CSC373 – Problem Set 1
To avoid suspicions of plagiarism: at the beginning of your submission, clearly state any resources (people, print, electronic) outside of your group, the course notes, and the course sta↵, that you consulted.
Problem Set: due September 30, 2016 22:00
Answer each question completely, always justifying your claims and reasoning. Your solution will be graded not only on correctness, but also on clarity.
Answers that are technically correct that are hard to understand will not receive full marks. Mark values for each question are contained in the [square brackets].
You may work in groups of up to THREE to complete these questions.
1 Minimizing Stops
You have a car that can travel d km on a full tank of gas. Your car starts out with a full tank of gas, you start at position 0, and you want to travel to position L. There are gas stations at positions g1, g2, . . . , gn. Each time you stop at a gas station, you fill your gas tank until it is full. Your goal is to minimize the number of gas-station stops that you make. Your gas tank is never allowed to become completely empty (otherwise your car stalls and you cannot keep going), and you can assume that the first gas station is within d km of the starting point, the last gas station is within d km of the ending point, and no two consecutive gas stations are more than d km apart.
1. [4] Give pseudocode for and prove a correct greedy algorithm for this problem. It’s required that you prove it in the way we have done in lecture. That is, give the greedy choice, define what it means for a partial solution to be promising, and then propose and prove an exchange argument that lets you incrementally change an optimal solution into your greedy solution without making the optimal solution worse.
2 Processor Scheduling
We have a processor on which n tasks are to be run. As soon as one task finishes running, the next one can start. Each task j has a length lj giving the amount of time that the task takes to run. Each task j also has a weight wj giving the importance of the task; tasks with higher weights are more important.
Define the completion time cj of a task j as the total time that elapses before task j finishes running. For example, if we run task 1 that has length 3 and then task 2 that has length 5, then the completion time of task 1 is 3, and the completion time of task 2 is 3 + 5 = 8.
We would like a greedy algorithm that minimizes the following quantity:
Xn
wj ⇤cj j=1
. (That is, we are minimizing the sum of the completion times but where each completion time is weighted by the importance of the task.) The output of the algorithm is a permutation of the jobs that minimizes this quantity.
1. [2] Give a plausible but incorrect greedy algorithm for this problem. Specifically, give the greedy choice that your algorithm uses, the algorithm pseudocode, and a counterexample showing that the algorithm is incorrect.
2. [6] Now give the pseudocode for and prove a correct greedy algorithm for this problem. It’s required that you prove it in the way we have done in lecture. That is, give the greedy choice, define what it means for a partial solution to be promising, and then propose and prove an exchange argument that lets you incrementally change an optimal solution into your greedy solution without making the optimal solution worse.
Think carefully through this proof and compare this problem to our scheduling problem from lecture. Notice that in lecture we had a set, and here we have a sequence; in lecture, we scheduled a subset of activities, but here we schedule all tasks. These di↵erences are important in the proof.
3 Fixing Roads
There is a road that goes from position 0 to position L, with N integer positions of road damage along the road. For example, we might have a road that goes from position 0 to position 20 (L = 20), with road damage at positions 5 and 8 (N = 2). The city has money to fix K positions of road damage, 0 K N. The city’s goal is to choose to fix the K damage positions in such a way as to maximize the minimum distance that a car can travel without hitting a damage position. In the above example, suppose that K = 1. Then the city should fix position 5, because, in doing so, a car travels at least 8 distance (position 0 to position 8) before hitting road damage. Had the city instead fixed the damage at position 8, then there would be a stretch of only 5 distance (position 0 to position 5) before the car hits road damage.
Here is a proposed greedy algorithm for this problem. Let D be the sequence of damage positions, additionally with 0 and L included. Once we fix a damage position, assume that we do not choose to fix it again.
sort D: D0 <= D1 <= ... for i in [1, 2, ..., K]:
find the leftmost q such that D_{q+1} - D_q is minimized
if q == 0: # fix first damage position
fix D_1 elif q == N: # fix last damage position
fix D_N else:
if D_q - D_{q-1} <= D_{q+2} - D_{q+1}:
fix D_q
else:
fix D_{q+1}
1. [4] Is this greedy algorithm correct? If so, prove it in the way that we have done in lecture. If not, give a counterexample and explain why the algorithm is incorrect.