Question 1. Constrained Scheduling Suppose you have a supercomputer that can run jobs one at a time. You have a set of jobs J that you need to run and wan to determine the best order in which to run them. Not ajobs take the same amount of time to complete; specifically, job jk takes time tk to complete. Each job must run to completion once started, so you can't pause or stop a job after starting it. Certain jobs depend on results computed by other jobs, so you cannot run the jobs in a completely arbitrary order. Specifically, you have a Directed Acyclic Graph (DAG) G = (J, E) whose nodes are the jobs J and where each edge (ji,id indicates that job j, must be run before job jk. Under these restrictions, i's easy to schedule all the jobs as efficiently as possible: ust topologically sort the DAG and run the jobs in that order Of course, there is a catch. Associated with each job jk is a cost function cosTk(t) denoting the cost of completing job jk at time t. These functions are monotonically increasing, so for any job je and any 0, we have cosT(t) 0, there is a DAG with n nodes and (n!) topological orderings. This shows the naifkve algorithm has worst-case runtime2(n!) Fortunately, we can improve upon the nafkve algorithm using dynamic programming. Let us call a set S .J a feasible set iff for every yk E S, if there is a path from Ji to Jk in G (i.e. Je depends on Ji), then J E S. Intuitively, a feasible set is a set of jobs that can be scheduled without missing any prerequisites. For example, in the following DAGs, the indicated nodes are feasible sets: For any feasible set S, let LAST(S) denote the set of all jobs ik E S such that (jk,Ji) E for any j E S. In other words, LAST(S) consists of all jobs in S that no other jobs depend on. (i) Prove that if S is a feasible set, then S is feasible for any j E LAST(S). For any feasible set S, let oFT(S) denote the optimal cost of scheduling the jobs in set S (iii) Prove that in any optimal schedule for the jobs in S, the supercomputer is never idle before all jobs have completed (i.e., obs have finished executing, the supercomputer is always executing some job.) (iv) Write a recurrence relation for oPT(S), then prove that your recurrence relation is correct. Given a recurrence relation for orT(S), it is possible to find the cost of an optimal schedule by using the following dynamic programming algorithm: .Let DP be a table of size 2 . For each subset S CJ, in an appropriate order: - IfS is feasible, Return DP[ J] in DP[S] based on the recurrence from (iv). If we assume each function cosT can be evaluated in time O(1), then (with the right recurrence relation for oPT(S) it is possible to fill each entry of DP in time O(n+m). It is also possible to check whether a set is feasible in time O(n+m). This means that the overall runtime for this algorithm is O(2"(n+m which is significantly better than the S2(n!) worst-case of the naifkve algorithm! Question 1. Constrained Scheduling Suppose you have a supercomputer that can run jobs one at a time. You have a set of jobs J that you need to run and wan to determine the best order in which to run them. Not ajobs take the same amount of time to complete; specifically, job jk takes time tk to complete. Each job must run to completion once started, so you can't pause or stop a job after starting it. Certain jobs depend on results computed by other jobs, so you cannot run the jobs in a completely arbitrary order. Specifically, you have a Directed Acyclic Graph (DAG) G = (J, E) whose nodes are the jobs J and where each edge (ji,id indicates that job j, must be run before job jk. Under these restrictions, i's easy to schedule all the jobs as efficiently as possible: ust topologically sort the DAG and run the jobs in that order Of course, there is a catch. Associated with each job jk is a cost function cosTk(t) denoting the cost of completing job jk at time t. These functions are monotonically increasing, so for any job je and any 0, we have cosT(t) 0, there is a DAG with n nodes and (n!) topological orderings. This shows the naifkve algorithm has worst-case runtime2(n!) Fortunately, we can improve upon the nafkve algorithm using dynamic programming. Let us call a set S .J a feasible set iff for every yk E S, if there is a path from Ji to Jk in G (i.e. Je depends on Ji), then J E S. Intuitively, a feasible set is a set of jobs that can be scheduled without missing any prerequisites. For example, in the following DAGs, the indicated nodes are feasible sets: For any feasible set S, let LAST(S) denote the set of all jobs ik E S such that (jk,Ji) E for any j E S. In other words, LAST(S) consists of all jobs in S that no other jobs depend on. (i) Prove that if S is a feasible set, then S is feasible for any j E LAST(S). For any feasible set S, let oFT(S) denote the optimal cost of scheduling the jobs in set S (iii) Prove that in any optimal schedule for the jobs in S, the supercomputer is never idle before all jobs have completed (i.e., obs have finished executing, the supercomputer is always executing some job.) (iv) Write a recurrence relation for oPT(S), then prove that your recurrence relation is correct. Given a recurrence relation for orT(S), it is possible to find the cost of an optimal schedule by using the following dynamic programming algorithm: .Let DP be a table of size 2 . For each subset S CJ, in an appropriate order: - IfS is feasible, Return DP[ J] in DP[S] based on the recurrence from (iv). If we assume each function cosT can be evaluated in time O(1), then (with the right recurrence relation for oPT(S) it is possible to fill each entry of DP in time O(n+m). It is also possible to check whether a set is feasible in time O(n+m). This means that the overall runtime for this algorithm is O(2"(n+m which is significantly better than the S2(n!) worst-case of the naifkve algorithm