HOMEWORK 11 FUNDAMENTAL ALGORITHMS

DUE April 26 A.Paz

  1. Exercise 4.19 (p 408) in the book

  2. Exercise 4.28 (p.409) in the book

  3. Given a UG G=(V,E), a spanning tree T of G, and a vertex v. Design an algorithm to determine whether T can be output as a DFS tree of G rooted at v, under some order of the adjaceny lists associated with the vertices of G. What is the complexity of your algorithm?

  4. A DAG is given as input for a topological sort problem. In addition, with every task vi a cost ti is associated, denoting the time required for performing task vi. Assume that you have an unlimited number of processors and that you can schedule as many tasks as feasible to be done in parallel by different processors. Describe an algorithm for assessing the time required in order to perform the whole job, under the above conditions. (it may be usefull to include dummy tasks B and E -for "begin" and "end" that take 0 time)