s
Section 5.2 Topological Sorting
363
5. Compute the minimum time to completion and the nodes on the critical path for the problem in Exercise 3.
6. Compute the minimum time to completion and the nodes on the critical path for the problem in Exercise 4.
7. For the problem in Exercise 3, great improvements in productivity have knocked down the time to perform task D from 6 units to 1 unit. Recompute the minimum time to completion and the nodes on the
critical path.
8. For the problem in Exercise 4, an extra quality-control step has been added to task 4, which now requires
4 units of time to perform. Recompute the minimum time to completion and the nodes on the critical path.
9. Do a topological sort on the partially ordered set shown.
H
G
D
A
C
F
B
E
10. Do a topological sort on the partially ordered set shown.
E
G
F
C
A
B
D
11. Find a topological sort for the problem in Exercise 3.
12. Find a topological sort for the problem in Exercise 4.
13. Given the following task chart for fixing an Asian dinner, find a total ordering in which the tasks can be
performed sequentially.
task
prerequisite tasks
1. Chop onions
9
2. Wash lettuce
11
3. Make dressing
11
4. Do stir fry
10
5. Toss salad
2, 3
6. Cut up chicken
None
7. Grate ginger
9
8. Chop bok choy
9
9. Marinate chicken
6
10. Heat wok
1, 7, 8, 11
11. Prepare rice
None