Algorithm Design and Analysis Assignment 3

    1. (25 points) Give a linear-time algorithm that takes as input a tree and determines whether it has a perfect matching: a set of edges that touch each node exactly once.

    2. (25 points) Consider you are a driver, and you plan to take highways from A to B with distance D. Since your car’s tank capacity C is limited, you need to refuel your car

at the gas station on the way. We are given n gas stations with surplus supply, they are located on a line together with A and B. The i-th gas station is located at di that means the distance from A to the station, and its price is pi for each unit of gas, each unit of gas exactly supports one unit of distance. Design e cient algorithms for the following tasks.

        (a) (5 points) Determine whether it is possible to reach B from A.

        (b) (20 points) Minimized the gas cost for reaching B.

    3. (25 points) The problem is concerned with scheduling a set J of jobs j1; j2; :::; jn on a single processor. In advance (at time 0) we are given the earliest possible start time si, the required processing time pi and deadline di of each job ji. Note that si + pi di. It is assumed that si, pi and di are all integers. A schedule of these jobs de nes which

job to run on the processor over the time line, and it must satisfy the constraints that each job ji starts at or after si, the total time allocated for ji is exactly pi, and the job nishes no later than di. When such a schedule exists, the set of jobs is said to be

feasible. We allow a preemptive schedule, i.e., a job when running can be preempted at any time and later resumed at the point of preemption. For example, suppose a job ji has start time 6, processing time 5 and deadline 990, we can schedule ji in one interval, say, [6; 11], or over two intervals [7; 8] and [15; 19], or even three intervals [200; 201], [300; 301], [400; 403].

        (a) (5 points) Give a set of jobs that is not feasible, i.e., no schedule can nish all jobs on time.

        (b) (20 points) Design an e cient algorithm to determine whether a job set J is feasible or not. Let D be the maximum deadline among all jobs, i.e., D = maxni=1 di, you should analyze the running time in terms of n and D. (Tips, you need to prove that if the input job set J is feasible, then the algorithm can nd a feasible schedule for J. )

        (c) (Bonus: 5 points) Design an e cient algorithm with the running time only in terms of n.






Page 1 of 2

    4. (25 points) Makespan Minimization Given m identical machines and n jobs with size p1; p2; :::; pn. How to nd a feasible schedule of these n jobs on m machines to minimize the makespan: the maximized completion time among all m machines?
Recallˆ that we have introduced two greedy approaches in the lecture.

GREEDY: Schedule jobs in an arbitrary order, and we always schedule jobs to the
    • earliest  nished machine.

LPT: Schedule jobs in the decreasing order of their size, and we always schedule jobs to the earliest nished machine.

We have proved that GREEDY is 2-approximate and LPT is 1:5-approximate, can we nish the following tasks? (Please write down complete proofs.)

    (a) (10 points) Complete the proof that LPT is 4=3-approximate, (i.e., LPT   4=3

OPT).

(b) (10 points) Prove that GREEDY is (2 1=m)-approximate, (i.e., GREEDY (2 1=m) OPT).


(c) (5 points) Prove that LPT is (4=3 1=3m)-approximate, (i.e., LPT (4=3 1=3m) OPT).



    5. How long does it take you to nish the assignment (include thinking and discussing)? Give a score (1,2,3,4,5) to the di culty. Do you have any collaborators? Write down their names here.
































Page 2 of 2