CS 170 Second Midterm 5 April 2007NAME (1 pt):TA (1 pt):Name of Neighbor to your left (1 pt):Name of Neighbor to your right (1 pt):Instructions: This is a closed book, closed calculator, closed computer, closed network, openbrain exam, but you are permited a 1 page, double-sided set of notes, large enough to readwithout a magnifying glass.You get one point each for filling in the 4 lines at the top of this page. Each other questionis worth the amount shown.Write all your answers on this exam. If you need scratch paper, ask for it, write your nameon each sheet, and attach it when you turn it in (we have a stapler).123Total21(1) Scheduling (30 points).• You’re an engineer planning the construction of a large bridge. There are constraintsbetween the tasks involved. For instance, a portion of road cannot be attached to thesuspensions until these are in place, or until the road itself is built. Let each task berepresented as a node in a graph, where a directed edge joins A to B if task A must becompleted before B begins.Give a condition on this graph for you to be able to order the tasks so as tosatisfy all the constraints.Answer. The graph must be a DAG.Give a method to check this condition.Answer. Run Depth First Search. The graph is a DAG if and only if no back-edge isfound.Give a method to find an ordering of the tasks that satisfies the constraintsif one exists.Answer. Run DFS and order the nodes by decreasing post number.• In fact in a real schedule, tasks can happen simultaneously, unless a constraint forces usto finish one before beginning the other.To represent task duration, let the length of edge A→B be the duration of A. (In otherwords, every outgoing edge from A must have the same length.) Let S (“Start”) and F(“Finish”) be special tasks of length 0, that must happen respectively before and after allother tasks. For instance they can represent the contract signature and the inauguration.An important concept in scheduling is the critical path, that is a sequence of tasksS, A1,...Ak,F such that Ai→ Ai+1and the length of the path is equal to that of theshortest possible schedule. We call this length the construction time.ADC FSBE0033221145Figure 1: A list of tasks (nodes), constraints (edges) and task durations (edge lengths).In Fig. 1, find the critical path and the construction time.Answer. The critical path is the longest path from S to F .HereitisS → A → C →E → F ,oflength9.Give a method to find the critical path automatically on a given graph (hint:this method uses the property of this graph that you found in the first partof this problem).2Answer. The best method is to adapt the “dags-shortest-path” method to find the longestpath instead. Find a linearization order as in the third question. Iterate through eachnode u in linearized order, calling update() on each edge from u, except update is now:update(u,v): dist(v) = max(dist(v),dist(u)+l(u,v))and the array dist() is initialized to −∞,orto0 since all durations are positive. We cancall this method “dags-longest-path”.• What we really want is not just the construction time, but an entire schedule, specifyingfor each task when to start it. How can you use the intermediate results of youralgorithm to output a start time for each task (each node)? Show that thisschedule is indeed valid, i.e. it does not violate any constraint.Answer. The array element dist(u) is the length of the longest path from S to u.Wecanuse it as start time. To prove that this gives us a valid schedule, look at a constraint u →v. The start time of u is dist(u), and the update equation gives us dist(v) ≥dist(u)+l(u, v)so the start time of v is after the end time of u.• If each task requires a team of workers, show how to compute the number of teamswe need to hire, i.e. the maximum number of tasks that will be executed inparallel. For example, if all tasks take unit time and A → B, A → C, B → D, C → D,then answer is 2 teams, because B and C can be done in parallel.Answer. Now that we have a starttime and end time for each task where start time isthe longest path to the vextex, and endtime = start time + task duration (lengths ofoutgoing edges), we can form records of the form (starttime,+1), (endtime, −1) andsort all the records by their first entry yielding the list (t1,s1), (t2,s2), ...(tn,sn) wheret1≤ t2≤ ... ≤ tnand each siis +1 or -1. If there are ties (multiple equal ti), then putall the records with si= −1 before the records with si=+1. Now doparalleltasks = 0;maxparallel tasks = 0;fori=1tonparalleltasks = parallel tasks + s i// increases by 1 when a new task starts// decreases by 1 when one endsmaxparallel tasks = max(max parallel tasks, parallel tasks)end3(1) Scheduling (30 points).• Planning the construction of a large building is a challenging engineering task, includingdealing with constraints among the tasks involved. For instance, a portion of roof cannotbe attached to the building until supports are in place, or until the roof itself is available.Let each task be represented as a node in a graph, where a directed edge joins A to B iftask A must be completed before B begins.Give a condition on this graph for you to be able to order the tasks so as tosatisfy all the constraints.Answer. The graph must be a DAG.Give a method to check this condition.Answer. Run Depth First Search. The graph is a DAG if and only if no back-edge isfound.Give a method to find an ordering of the tasks that satisfies the constraintsif one exists.Answer. Run DFS and order the nodes by decreasing post number.• In fact in a real schedule, tasks can happen simultaneously, unless a constraint forces usto finish one before beginning the other.To represent task duration, let the length of edge A→B be the duration of A. (In otherwords, every outgoing edge from A must have the same length.) Let S (“Start”) and F(“Finish”) be special tasks of length 0, that must happen respectively before and after allother tasks. For instance they can represent the contract signature and the inauguration.An important concept in scheduling is the critical path, that is a sequence of tasksS, A1,...Ak,F such that Ai→ Ai+1and the length of the path is equal to that of theshortest possible schedule. We call this length the construction time.ADC FSBE0033221145Figure 2: A list of tasks (nodes), constraints (edges) and task durations (edge lengths).In Fig. 2, find the critical path and the construction