Imagine you are the main contractor building a large skyscraper. You are promised a huge bonus if you can finish the job fast. Obviously, there are some constraints; you cannot install windows until you have built the walls. However, you can easily install windows and doors at the same time, while also painting the walls. You want to get an estimate on how long it will take you to build the skyscraper. (You may assume that each task is taking exactly one day to finish.) You have enough resources to perform independent tasks simultaneously.

(a) ( 2 points) Find how to represent this problem by using a directed graph. Make sure to give a precise description of how nodes, edges and directions are assigned.

(b) (1 point) You want to find out whether it is even possible to build the building. For this you need to know that there are no two jobs that mutually depend on each other. (e.g. j1 needs to be finished before j2, but j2 needs to be finished before j1). Formulate what property your graph needs to have so that this doesnt happen. Give a one sentence explanation why.

(c) ( 5 points) Assume you are given a directed graph G in an adjacency list format. You want to find all nodes that currently have indegree 0 and delete the nodes and their adjacent edges from G. Find a (m + n) algorithm UpdateGraphAndDegrees to do this. Your algorithm takes the graph adjacency list as an input. It returns two objects; 1. the updated adjacency list of G after the deletions 2. an array indegree that contains the in-degree of node i in indegree[i]. The in-degree of the removed nodes in this array should be set to 0. (You may assume that nodes are indexed 1, . . . n.)

(d) ( 8 points) Find an algorithm that returns the order in which tasks should be executed. Your algorithm will return an array A of tuples, such that the tuple in A[i] consists of the tasks that can be executed on day i. Hint: in each iteration find all the nodes with zero indegree and remove. To do this efficiently you may find the algorithm from part c useful.