HOMEWORK 11 FUNDAMENTAL ALGORITHMS
DUE April 26 A.Paz
- Exercise 4.19 (p 408) in the book
- Exercise 4.28 (p.409) in the book
- 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?
- 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)