Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionii [2012/02/26 20:56] – [Designing the algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapterfour_sectionii [2012/02/26 22:13] (current) – [Designing the algorithm] mugabej
@@ Line 26: / Line 26: @@
 >>>>>>>>>> Order the jobs in order of their deadlines  --> Takes O(nlogn) time
->>>>>>>>>>Assume d<sub>1</sub>≤ d<sub>2</sub> ≤ d<sub>3</sub>,...,d <sub>n-1</sub> ≤ d<sub>n</sub>
+>>>>>>>>>>Assume d<sub>1</sub> ≤ d<sub>2</sub> ≤ d<sub>3</sub>,...,d <sub>n-1</sub> ≤ d<sub>n</sub>
 >>>>>>>>>>Initially //f// = s   --> Takes O(1) time
 >>>>>>>>>> Consider the jobs i= 1,2,...,n in this order
@@ Line 36: / Line 36: @@
 === Algorithm Analysis ===
-  * //Exchange Argument//: Gradually modifying an optimal schedule,conserving its optimality at each step, but eventually transforming it into a schedule similar to the schedule given by the greedy algorithm so to prove the optimality of the latter.
+  * //Exchange Argument//: Gradually modifying an optimal schedule,conserving its optimality at each step, but eventually transforming it into a schedule similar to the schedule given by the greedy algorithm to prove the optimality of the latter.
+  * There is an //inversion// if a job //i// with deadline d<sub>i</sub> is scheduled before another job //j// with deadline d<sub>j</sub>
+  * The greedy algorithm has no idle time and by definition,no inversions. There is an optimal schedule with no idle time.
+  * All schedules with no inversions and no idle time have the same maximum lateness.
+  * There is an optimal schedule that has no inversions and no idle time.
+  * As a consequence, the schedule produced by the greedy algorithm has optimal maximum lateness
+--> For proofs of the above claims,see the book of the course
+\\
+\\
+I give this section an 8/10 for being brief and concise in its explanation of the material.