Problem 3. (20 pts)lprogramming assignment] Consider a different version of the job scheduling problem in 4.2 that now minimizes the weighted sum of job completion times. In this version, each of n jobs has a weight wi and a duration ti and all must be scheduled in serial order, starting at time zero (with no slack). A schedule S is therefore an ordering of the jobs, and the comple- tion time of jobi in S, C(S), is defined to be the sum of the durations tk of all jobs (including i) that precede i in S. Find the schedule S* that minimizes over all S: -lwiCi(S). Input (stored in a file called jobs.csv): Comma-separated wi, ti pairs of integers, one pair per line. Output (printed to command line): Optimal permuted ordering of the jobs, like: 4, 3, 1, 5, 6, 2. 1. Provide a counterexample to the optimality of ordering by heaviest-weight first. I1 pt] 2. Provide a counterexample to the optimality of ordering by shortest-job first. pt 3. Design and analyze an efficient algorithm for computing an optimal schedule.* Hint: to prove optimality, use an exchange argument, similar to the one used for minimizing lateness in 4.2. (*) For this problem you should submit a source file in Java, with your code and comments explaining the steps and analyzing its running time. Problem 3. (20 pts)lprogramming assignment] Consider a different version of the job scheduling problem in 4.2 that now minimizes the weighted sum of job completion times. In this version, each of n jobs has a weight wi and a duration ti and all must be scheduled in serial order, starting at time zero (with no slack). A schedule S is therefore an ordering of the jobs, and the comple- tion time of jobi in S, C(S), is defined to be the sum of the durations tk of all jobs (including i) that precede i in S. Find the schedule S* that minimizes over all S: -lwiCi(S). Input (stored in a file called jobs.csv): Comma-separated wi, ti pairs of integers, one pair per line. Output (printed to command line): Optimal permuted ordering of the jobs, like: 4, 3, 1, 5, 6, 2. 1. Provide a counterexample to the optimality of ordering by heaviest-weight first. I1 pt] 2. Provide a counterexample to the optimality of ordering by shortest-job first. pt 3. Design and analyze an efficient algorithm for computing an optimal schedule.* Hint: to prove optimality, use an exchange argument, similar to the one used for minimizing lateness in 4.2. (*) For this problem you should submit a source file in Java, with your code and comments explaining the steps and analyzing its running time