Suppose you are running a business and you get, on day one, a set of n jobs 1, 2, . . . , n. For each job, you will get $100 less one dollar per day it takes you to complete the job. You can only work on one job at a time and once you start a job, you must complete it. You know, on day one, how many days each job will take. You must complete all the jobs. You want to work on the jobs in an order that will maximize your profit.

Formally, job j takes tj days to complete. An ordering of the jobs will define a completion time Cj for each job j. That is, if the first job in the ordering is j, then the completion time will be Cj = tj . The completion time of any other job j 0 is given by the completion time of the job before it in the ordering plus tj 0 . You want to maximize 100n Pn j=1 Cj which is equivalent to minimizing Pn j=1 Cj . (

a) Design a greedy algorithm to find an ordering (and so define completion times) that minimizes Pn j=1 Cj . Give pseudocode for this algorithm.

(b) Prove that your algorithm correctly minimizes Pn j=1 Cj .

(c) What is the running time of your algorithm?