You will solve another scheduling problem. Say you run a workshop and you get a set of n tasks that your clients give you. Task i takes ti time. In addition, each task has a priority pi$.$ You can only do these tasks one at a time.

The completion time fi of a task i is the time at which it completes $$ therefore, if you do the tasks in order $1,2,3,4...,$ then the completion time of task $1$ is f$1=$ t$1,$ the completion time of task $2$ is f$2=$ t$1+$ t$2($since it has to wait until task $1$ is done before it can start$)$ and completion time of task $3$isf$3=$t$1+$t$2+$t$3....$

Your goal is to minimize the cost function

n

C $=$ Xpifi

i$=1$

where fi is the completion time of task i$.$ That is$,$ you are minimizing the weighed sum of com$-$ pletion times. You will design, prove the correctness of$,$ and analyze a greedy algorithm for this problem.

$($a$)[15$ points$]$ Consider some simple greedy strategies. a$)$ Schedule the shortest job first. b$)$ Schedule the job with the biggest priority first. Give counter$-$examples for both these strategies.