364
Relations, Functions, and Matrices
14. A U.S. journalist, on being posted to a bureaucratic foreign country, was faced with the following tasks
before she could begin work.
task
prerequisite tasks
1. Obtain a residence permit from the Public Security Bureau
2, 3, 7
2. Obtain a health certificate from the local hospital
None
3. Obtain a journalist work card from the Foreign Ministry
None
4. Obtain a customs certificate from the Customs Office
1, 3, 9
5. Post an announcement in the local newspaper about the presence of her news company in the country
None
6. Obtain a journalist visa from the Public Security Bureau
2, 3, 7
7. Obtain a foreign journalist housing contract from the local
housing authority
None
8. Pick up her shipment of belongings from the United States
1, 4, 6
9. Obtain a news organization permit from the Foreign Ministry.
5
Find a total ordering in which the tasks can be performed sequentially.
15. Recall the problem posed at the beginning of this chapter:
Your company has developed a program for use on a small parallel processing machine. According to
the technical documentation, the program executes processes P1, P2, and P3 in parallel; these processes
all need results from process P4, so they must wait for Process P4 to complete execution before they
begin. Processes P7 and P10 execute in parallel but must wait until Processes P1, P2, and P3 have
finished. Process P4 requires results from P5 and P6 before it can begin execution. P5 and P6 execute
in parallel. Processes P8 and P11 execute in parallel but P8 must wait for Process P7 to complete, and
Process P11 must wait for P10 to complete. Process P9 must wait for results from P8 and P11. You have
been assigned to convert the software for use on a single processor machine.
Use a topological sort to determine the order in which the processes should be executed sequentially.
16. Given the following task chart for conducting a water quality study, find a total ordering in which the tasks
can be performed sequentially.
task
prerequisite tasks
1. Plan schedule
7
2. Collect new data
1, 10
3. Assemble team
7
4. Collect prior water quality data
6
5. Obtain equipment
7
6. Identify streams
None
7. Decide on readings needed
4, 8
8. Review federal and state guidelines
None
9. Write report
11
10. Distribute equipment
3, 5
11. Analyze new data
2
Relations, Functions, and Matrices
14. A U.S. journalist, on being posted to a bureaucratic foreign country, was faced with the following tasks
before she could begin work.
task
prerequisite tasks
1. Obtain a residence permit from the Public Security Bureau
2, 3, 7
2. Obtain a health certificate from the local hospital
None
3. Obtain a journalist work card from the Foreign Ministry
None
4. Obtain a customs certificate from the Customs Office
1, 3, 9
5. Post an announcement in the local newspaper about the presence of her news company in the country
None
6. Obtain a journalist visa from the Public Security Bureau
2, 3, 7
7. Obtain a foreign journalist housing contract from the local
housing authority
None
8. Pick up her shipment of belongings from the United States
1, 4, 6
9. Obtain a news organization permit from the Foreign Ministry.
5
Find a total ordering in which the tasks can be performed sequentially.
15. Recall the problem posed at the beginning of this chapter:
Your company has developed a program for use on a small parallel processing machine. According to
the technical documentation, the program executes processes P1, P2, and P3 in parallel; these processes
all need results from process P4, so they must wait for Process P4 to complete execution before they
begin. Processes P7 and P10 execute in parallel but must wait until Processes P1, P2, and P3 have
finished. Process P4 requires results from P5 and P6 before it can begin execution. P5 and P6 execute
in parallel. Processes P8 and P11 execute in parallel but P8 must wait for Process P7 to complete, and
Process P11 must wait for P10 to complete. Process P9 must wait for results from P8 and P11. You have
been assigned to convert the software for use on a single processor machine.
Use a topological sort to determine the order in which the processes should be executed sequentially.
16. Given the following task chart for conducting a water quality study, find a total ordering in which the tasks
can be performed sequentially.
task
prerequisite tasks
1. Plan schedule
7
2. Collect new data
1, 10
3. Assemble team
7
4. Collect prior water quality data
6
5. Obtain equipment
7
6. Identify streams
None
7. Decide on readings needed
4, 8
8. Review federal and state guidelines
None
9. Write report
11
10. Distribute equipment
3, 5
11. Analyze new data
2