Hints for Final (CS U690)

For the final exam, please note:
  1. Question 3 should have the equation fi=si+ti instead of fi=si+t+i.
  2. The second paragraph of question 4 should have been a separate problem. The second paragraph will be graded as a separate problem, worth 5 points. This makes for a total of 115 points possible on the final, of which 15 points is extra credit.
The following hints were discussed in the class on Monday morning.
  1. HINT: Question 3: First prove that the greedy algorithm as stated works for the case of only two jobs, instead of n jobs. This is easy. (There are only two possible schedules: either job l1 is done first, or job 2 is done first.) Then show the general case by arguing that two or more jobs can be considered as if they were a single job. This makes the problem simpler. The chapter on the greedy algorithms in the textbook uses ideas like this.
  2. HINT: Question 4 (first paragraph): This problem is probably one of the harder problems of the exam. Nevertheless, it is not too hard. Again, consider the case of only two jobs. Find an algorithm for choosing the schedule with the smallest penalty.

    Assume that the first schedule finishes job 1 at time f1 and finishes job 2 at time f2. Assume that the second schedule finishes job 2 at time f'2 and then finishes job 1 at time f'1. We want to know if w1f1+w2f2 is greater than w2f'2+w1f'1

    We then conclude that f2=f'1. We also conclude that f1 = f'1 - f'2 since both are equal to t1, the duration of job 1.

    Putting it all together, we use the two queations to eliminate two out of the four quantitites, f1, f2, f'1, and f'2. We then write down our test in terms of only two of the "f" variables, and w1 and w2.

    Now, we know the test or algorithm for two jobs. We need to derive an algorithm for n jobs.