Starting from:
$30

$24

Homework #9 Solution

Problem 1 (6.2 from text)

Describe a mathematical model for the following scheduling problem. Given tasks T1, T2, . . . , Tn, which require times t1, t2, . . . , tn to

complete, and a set of constraints, each of the form "Ti must be completed prior to the start of Tj," find the minimum time necessary to complete all tasks.







Problem 2 (6.8 from text)

Assuming the order of the vertices is a, b , . . . , f in Fig. 6.38, construct a depth-first spanning forest; indicate the tree, forward, back and cross arcs,

and indicate the depth-first numbering of the vertices.













Problem 3 (6.10 from text)

A root of a dag is a vertex r such that every vertex of the dag can be reached by a directed path from r. Write a program to determine whether a dag is rooted.




Problem 4 (6.14 from text)

Write a program to find the longest path in a dag. What is the time complexity of your program?







Problem 5 (6.15 from text)

Find the strong components of Fig. 6.38.




Solution

Strongly connected components:

a
e
b,c,d,f



Problem 6 (6.20 from text)

Write a program that takes as input a digraph and two of its vertices. The program is to print all simple paths from one vertex to the other. What is the time complexity of your program?




Problem 7 (7.3c from text)

Consider the graph of Fig. 7.20.

Find a depth-first spanning tree starting at a and at d.

More products