Question & Answer: Choose one of the theorems about optimality of scheduling algorithms and prove it.it is necessa…..

ANSWER::

We will prove that the schedule S provided by the Greedy algorithm shown in class schedules n events at least as quickly as any other competing schedule S’.

Base case: n=1. Because S schedules the event that finishes first out of all possible events, S must finish scheduling 1 event before or exactly when S’ does.

Inductive hypothesis: Assume for an arbitrary value of n=k that S schedules k events at least as quickly as any competing schedule S’. (We can say that S has an ending time of t while any competing schedule S’ has an ending time of t’, and that the hypothesis is that t £ t’.)

Inductive step: Prove for n=k+1 that S schedules k+1 events at least as quickly as any competing schedule S’.

In order to prove the inductive step, we start with the inductive hypothesis. We know that that t £ t’. Thus, S is allowed to schedule any event with a start time greater than or equal to t, while S’ is allowed to schedule any event with a start time greater than or equal to t’. Thus, S is allowed to schedule any event S’ is allowed to schedule. Of those allowable events, if S chooses one, it will be the one that finishes first. It would be impossible for S’ to pick one from the set that finishes before the one that finishes first in the set. Thus, we have shown for n=k+1, that S schedules k+1 events at least as quickly as S’ does.

Proof #2 by contradiction

We will assume to the contrary that there exists a schedule S’ that schedules more events than the schedule S given by the greedy algorithm. If this is the case, then there is a time t, 0 < t £ m, at which S’ has completed k events while S has completed less than that. (k is a positive integer.) Let t be the minimum such time. Clearly, t occurs when the k^th event in schedule S’ finishes. Now, denote the time that the (k-1)^thevent in S’ finishes as t’. Since t is the minimum time at which S’ finished more events than S, we know that at time t’, S has finished at least as many events as S’. Thus, S has finished (k-1) events or more by time t’. When S chooses it’s k^th event, it chooses the one that finishes first of the ones available. Clearly, the event chosen by S’ is available at this point in time. Thus, S must choose it or another that ends at or before when it ends. BUT, this contradicts the fact that S’ has finished more events than S at time t. Thus our assumption, that there was a point in time where S’ has finished more events than S is false. Thus, S is optimal.