276 Relations, Functions, and Matrices
Exercises 4.2
1. The following tasks are required in order to assemble a bicycle. As the manufacturer, you
must write a list of sequential instructions for the buyer to follow. Will the sequential
order given below work? Giveanother sequence that could be used.
Task Prerequisite Tasks
1. Tightening frame fittings None
2. Attaching handle bars to frame 1
3. Attaching gear mechanism 1
4. Mounting tire on wheel assembly None
5. Attaching wheel assembly to frame 1,4
6. Installing brake mechanism 2,3,5
7. Adding pedals 6
8. Attaching seat 1
9. Adjusting seat height 7,8
Construct
\342\200\242kl. a PERT chart from the following task table.
Task Prerequisite Tasks Timeto Perform
A E 3
B C,D 5
C A 2
D A 6
E None 2
F A,G 4
G E 4
H B,F 1
3. Construct a PERT chart from the following task table.
Task Prerequisite Tasks Time to Perform
1 2 4
2 3 2
3 8 5
4 3 2
5 4,7 2
6 5 1
7 3 3
8 None 5
\342\200\2424.
Compute the minimum time to completion and the nodes on the critical path for the
problem in Exercise 2.
5. Compute the minimum time to completion and the nodes on the critical path for the
problem in Exercise 3.
Section 4.2 Topological Sorting 277
6. Do a topological sort on the partially ordered set shown in the accompanying figure.
*7. Find a topological sort for the problem in Exercise 2.
8. Find a topological sort for the problem in Exercise 3.
9. Given the following task chart, 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. Chopbok choy 9
9. Marinate chicken 6
10. Heat wok 1,7,8,11
11. Prepare rice None
10. A U.S. journalist, on being posted to a bureaucratic foreign country, was faced with the
following tasks before she couldbegin work.
Task Prerequisite Tasks
1. Obtain a residencepermit 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 U.S. 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.
278 Relations, Functions, and Matrices
11. 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 PI, P2, and P3 in
parallel; these processes all need results from process P4, so they must wait for Process P4 to
completeexecution before they begin. Processes P7 and P10 execute in parallel but must wait
until processes PI, 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 PI 1 execute in
parallel but P8 must wait for process P7 to complete, and process PI 1 must wait for P10 to
complete. ProcessP9 must wait for results from P8 and PI 1. You have been assigned to
convert the software for use on a single processor machine.
Usea topological sort to determine the order in which the processes should be executed
sequentially.
Section 4.3 Relations and Databases
A database is a associatedinformation
storehouse of about some enterprise. The user of a
database can certainly some specific fact stored
retrieve in the database. But a well-designed
databaseis more than simply a list of facts. The user can perform queries on the database to
retrieve information not contained in any single fact. The whole becomes more than the sum
of its parts.
To design a useful and efficient computerized database, it is necessary to modelor
represent the enterprise with which the database is concerned. A conceptual model attempts to
capture the important features and workings of the enterprise. Considerable interaction with
those who are familiar with the enterprise may be required to obtain all the information
necessaryto formulate the model.
Entity-Relationship Model
One high-level representationof an enterprise is the entity-relationship model. In this model,
important objects, or
entities, in the enterprise are identified, together with their relevant
attributes or properties. Then the relationships between these various entities are noted. This
information is represented graphically by an entity-relationship diagram, or E-R diagram.
In an E-R diagram, rectangles denote entity sets, ellipses denote attributes, and diamonds
denoterelationships.
EXAMPLE 19 The Pet Lovers of America Club (PLAC) wants to set up a database. PLAC
has bought mailing lists from commercial sources, and it is interested in those people who
own pets and in some basic information about those pets, such as the name, type of pet (dog,
cat, etc.),and the breed.
Figure 4.10 shows an E-R diagram for the PLAC [Link] diagram says that
persons and pets are the entities. Personshave the attributes of Name, Address, City, and State.
Pets have the attributes Pet-type, and Breed. The diagram
of Pet-name, also shows that persons
own pets. Thinking of the entities as sets, the Person set and the Pet set, the relationship
\"owns\" is a binary relation from Person to Pet\342\200\224theownership relation is captured by (person,
