IE172 – Algorithms in Systems Engineering Final Exam, 04/29/2009Exercise 1: Breadth First search (20 pts.). Consider the digraph in thefigure on the next page, and suppose you want to generalize the Breadth FirstSearch (BFS) algorithm to directed graphs.1. Given that we have discussed the BFS on undirected graphs, will a BFSprocedure for digraphs look different? Discuss the differences, if any.2. What data structure is needed to keep track of the nodes yet to be visited?3. Apply the digraph version of the BFS to the following graph. The BFSstarted at node 1, and has already visited nodes 2 and 5 as shown by thecolors and distances d[i]. Report the operations you make in the order andhow the fundamental data structure for BF S changes, and the final value ofd[i] for every node, and the predecessor of each node (not in the graph, butcan be inferred).123456d[1] = 0d[2] = 1d[3] = ∞d[4] = ∞d[5] = 2d[6] = ∞Exercise 2: Precedence graphs (15 pts.). The graph below depicts the orderin which some operations have to be carried out in a car manufacturing plant.An arc (i, j) tells you that operation j cannot be started before i is finished.1. What are the fundamental phases of the algorithm you would use to findout the correct order for these task?2. Run the algorithm and write the operations in the list below, in the orderin which the operations should be carried out.ABCDEGHIJ1: .................. 4: .................. 7: ..................2: .................. 5: .................. 8: ..................3: .................. 6: .................. 9: ..................Exercise 3: Shortest paths (15 pts.). Dijkstra’s algorithm is a sort of BFSthat uses a particular data structure S to hold the nodes yet to be visited.1. What is that data structure S?2. On what class of graphs does Dijkstra’s algorithm not work?3. Run Dijkstra’s algorithm in the graph below, with source node 1, for twoiterations only (stop after extracting two nodes from S). Describe, for eachof the two iterations, what node is drawn from S and what other operationsare performed (e.g.: change in predecessors, distances, etc.).123457462953Exercise 4: Linear Algebra (15 pts.). Solve the system of linear equations:2x1+3x3= 54x1+x2= 4+x2+x3= 31. reduce the system to one where the coefficient matrix is upper triangular;2. compute the value of the variables using the modified system.Exercise 5: Algorithm design (15 pts.). Consider an undirected graphG = (V, E) such that:– all nodes in a subset S ⊆ V , given as input, are colored green;– the remaining nodes are not colored yet;– each node is associated with a weight wi.1. Write the pseudocode of an algorithm to color red all the nodes of V \ S (i.e.,those not yet colored) that have at most two green neighbors and such thatthe total weight of the red nodes is maximum.2. What is the worst-case complexity of the algorithm?Exercise 6: Dynamic Programming (20 pts.). Consider the problem:You have to schedule a plant producing liquid nitrogen for the next nshifts of eight hours each. At the beginning of each shift, the pr oductionrate can be set to either a nominal production rate of Aitons/hour orto a peak rate of Bitons/hour.The electric power required for production depends on the air temper-ature at the beginning of each shift: it is ciwhen producing at rate Aiand diwhen producing at rate Bi. Clearly, Ai< Biand ci< di, for alli = 1, 2 . . . , n.Decide the production rate for each of the n shifts so that the total energyconsumption is at most F and the total production is maximized. Allparameters Ai, Bi, ci, di, F are known in advance.Devise a Dynamic Programming algorithm for the problem. Identify stages andstates, and clearly explain what each stage and each state is associated with.Also explain how the solution would be computed if we used recursion, and howinstead it should be computed from the bottom up.Exercise 7: Linear Algebra (20 extra points). Prove that the followingmatrix is singular using one of the techniques seen during the course:A =4 5 38 1 −13 6