Please ans both part as it is one question. And explain as much as possible.

4. [25%] The following two parts guide you through the design of a scheduling algorithm. Part (a) gives you the insights you need for finishing part (b). (a) (10%) You have a beefy compute server and you have n computing jobs (1, 2, ... n). While the server is super fast, it can only serve one job at a time. Job i will run for a duration of di. To schedule job i, you set the start time si. The finish time fi will then be si + d. Only when a job is finished can the next job begins. The server is available for serving jobs at time 0. You want to schedule the jobs in such a way that the average finish time is minimized. That is, you want to make the following quantity as small as possible: n 1 f. (5) n i=1 Design an efficient algorithm that computes the optimal schedule for the jobs. Justify the correctness and analyze the running time of your algorithm. (b) (15%) Suppose some jobs are more "valuable than others, and thus the average finish time as listed in (5) does not fully capture this fact. More specifically, the relative value of job i is reflected in a weight wi (where wi > 0). So we would like to minimize the following quantity instead: n (w;- fi) (6) i=1 Design an efficient algorithm that computes a schedule that minimizes (6). Justify the correctness and analyze the running time of your algorithm