4. 25 pointecal the Scheduling to Minimize Lateness problem. The input is a list of "jobs" each of which requires a length of time t and has a deadline d,. A schedule is an ordering (permutation) of the jobs, to be done one right after another, and s(i) and f(i) denote the start and finish times of job i under a particular schedule. The lateness is defined to be f(i - di if job i is late (i.e., f(i) > d or 0 if job i is not late. We proved that a greedy algorithm which simply sorts the jobs in increasing order of deadline minimizes the maximum lateness over all jobs (max, Li,) Now we consider a variant of the problem, with two changes. First, we redefine the lateness 6 to be f(i) _ di regardless of whether job i s late (so Ii is negative ifjob i is early). Second, we consider the total lateness ( li) rather than the maximum. Thus, one job being finished early can "offset another job being late. 4a. 10 points Find an input with two jobs on which the "earliest deadline first greedy algorithm fails to find an optimal schedule 4b. 15 points) Use an exchange argument to prove that the "shortest job fis greedy algorithm actually produces an optimal schedule. That is, assuming the jobs have been renumbered so t1 St2 SSln, show that this algorithm's sehedule A (1,2,... ,n) is at least as good as any other schedule B. The analysis is structured just like the exchange argument we saw in class: Imagine "BubbleSorting" B to A by repeatedly picking a consecutive inversion and swapping i, and argue that in each step the total lateness doesn't increase. To be precise, consider any step where a consecutive inversion (i,j) is being swapped (so i >j but i was scheduled immediately before j), and for eaclh job k let s'(k), f'(k), be its start time, finish time, and lateness in the "before the swap" schedule, and similarly s"(k),f"(k),eg in the "after the swap" schedule. Then s'(i) s"j) and f')-f"(i), and for each k other than i and j, job k's contribution to the total lateness doesn't change in this step since f'(k) f"(k). Thus it just remains to show that +ljs+ 4. 25 pointecal the Scheduling to Minimize Lateness problem. The input is a list of "jobs" each of which requires a length of time t and has a deadline d,. A schedule is an ordering (permutation) of the jobs, to be done one right after another, and s(i) and f(i) denote the start and finish times of job i under a particular schedule. The lateness is defined to be f(i - di if job i is late (i.e., f(i) > d or 0 if job i is not late. We proved that a greedy algorithm which simply sorts the jobs in increasing order of deadline minimizes the maximum lateness over all jobs (max, Li,) Now we consider a variant of the problem, with two changes. First, we redefine the lateness 6 to be f(i) _ di regardless of whether job i s late (so Ii is negative ifjob i is early). Second, we consider the total lateness ( li) rather than the maximum. Thus, one job being finished early can "offset another job being late. 4a. 10 points Find an input with two jobs on which the "earliest deadline first greedy algorithm fails to find an optimal schedule 4b. 15 points) Use an exchange argument to prove that the "shortest job fis greedy algorithm actually produces an optimal schedule. That is, assuming the jobs have been renumbered so t1 St2 SSln, show that this algorithm's sehedule A (1,2,... ,n) is at least as good as any other schedule B. The analysis is structured just like the exchange argument we saw in class: Imagine "BubbleSorting" B to A by repeatedly picking a consecutive inversion and swapping i, and argue that in each step the total lateness doesn't increase. To be precise, consider any step where a consecutive inversion (i,j) is being swapped (so i >j but i was scheduled immediately before j), and for eaclh job k let s'(k), f'(k), be its start time, finish time, and lateness in the "before the swap" schedule, and similarly s"(k),f"(k),eg in the "after the swap" schedule. Then s'(i) s"j) and f')-f"(i), and for each k other than i and j, job k's contribution to the total lateness doesn't change in this step since f'(k) f"(k). Thus it just remains to show that +ljs+