Exam III
Discrete Structures I
Do all steps with detailed explanations.
1. (15 points)
(a) How many bit strings of length 8 are there? Explain.
(b) How many bit strings of length 8 are there which begin with a 0 and end with a 0? Explain.
(c) How many bit strings of length 8 are there which contain at most 3 ones? Be careful with this one. Explain. (See your notes, week 10.)
(d) How many bit strings of length 8 are palindromes?
3. (10 points)
(a) Text, page 405, number 16. Explain.
How many numbers must be selected from the set {1,3,5,7,9,11,13,15} to guarantee that at least one pair of these numbers add up to 16?
(b) Text, page 406, number 36. Explain
A computer network consists of six computers. Each computer is directly connected to at least one of the other computers. Show that there are at least two computers in the network that are directly connected to the same number of other computers.
3. (10 points).
Text, page 414, number 30. Explain.
Seven women and nine men are on the faculty in the mathematics department at a school.
a) How many ways are there to select a committee of five members of the department if at least one woman must be on the committee?
b) How many ways are there to select a committee of five members of the department if at least one woman and at least one man must be on the committee?
4. (10 points)
(a) Use the Binomial Theorem to write the expansion of (x + y) 6?
(b) Write the coefficient of the term x2y4z5 expansion of (x + y + z) 11. See example 12 in your notes of week 10
5. Study pages 1-4 of the notes for week 11. Let A = {a, b, c, d}, and let R be the relation defined on A by the following matrix:
MR =
1010
0110
0011
1101
éù
êú
êú
êú
êú
ëû
(a) (10 pts.) Describe R by listing the ordered pairs in R and draw the digraph of this relation.
(b) (15 pts.) (Note this is similar to exercise 7 page 630. Which of the properties: reflexive, antisymmetric and transitive are true for the given relation? Begin your discussion by defining each term in general first and then how the definition relates to this specific example.
(c) (5 pts.) Is this relation a partial order? Explain. If this relation is a partial order, draw its Hasse diagram.
6. (10 points) Note, this is similar to number 25, page 631). Consider the following Hasse diagram of a partial ordering relation R on a set A:
e
(a) List the ordered pairs that belong to the relation. Keep in mind that a Hasse diagram is a graph of a partial ordering relation so it satisfies the three properties listed in number 5 part (b).
(b) Find the (Boolean) matrix of the relation.
7. (15 points) Before you do this problem study the example at the end of the exam, as well as the notes in weeks 12 and 13.
Assume the Boolean matrix below is MR and that MR represents the relation R where R represents the connecting flights that an airline has between 4 cities: a, b, c, and d.
The 1 in row a column b means there is a flight from city a (Manchester) to city b (Boston). In general there is a 1 in row x column y iff there is a connecting flight between (from) city x and (to) city y That is, the rows of the matrix represent the cities of the origins of the flights and the columns represent the destination cities.
Let MR =
abcd
a1100
b0110
c0011
d1100
éù
êú
êú
êú
êú
ëû
(i) Let a stand for the airport in the city of Manchester, let b stand for the airport in Boston, c stand for the Chicago airport, d for the airport in the city of Denver. Is their a flight from Denver to Chicago? Explain.
(ii) Compute and interpret the Boolean products: MR 2, and MR 3. (Remember to use Boolean arithmetic). What do these Boolean products give you? That is, explain what the Boolean entries in the matrices MR 2 and MR 3 mean.
(iii) Now call the given matrix A and compute A2 and A3 , using regular, not Boolean arithmetic. What do these products give you?
(v) What does MR + M2R + M3R + M4R give you? Note, this is Theorem 3 page 602where the text’s symbol, v, for Boolean addition is replaced by +, another symbol for Boolean addition .
Bonus questions
1. Make up a question using the idea of question 7 (Something you do at work, home, something you’re interested in.) See 3 below for an example you can do.
2. In your notes of week 12 Project Evaluation and Review Technique (PERT) is explained. Make up a meaningful example illustrating this process. Explain all details. Draw the graphs involved. You should use a reasonable number of tasks.
(a) Determine the minimum time needed to complete your set of tasks.
(b) Determine the Critical Path for your example. Explain what this gives you.
(c) Comment on your example. Which task(s) cause a delay in the project? How would you fix the problem? Can you obtain more information out of your example?
3. The Network analysis problem.
4. Read Program Evaluation and Review Technique (PERT) in your week 14 notes. Note the examples given here are a little “ambitious”. Make up an example using PERT and find and explain the critical path of your example. Google “critical path analysis”, for more ideas.
If #7 is not clear here is an example which may help you to understand #7
Let D = days of the week {M, T, W, R, F},
E = {Brian (B), Jim (J), Karen (K)} be the employees of a tutoring center at a University and let
U = {Courses the tutoring center needs tutors for}
= {Calculus I (I), Calculus II (II), Calculus III (III), Computers I (C1), Computers II (C2), Precalculus (P)}.
We define the relation R from D into E by d R e, if employee e is scheduled to work on day d. We also define S from E into U by e r u, if employee e is capable of tutoring students in course u.
For example, the matrix MR indicates that on R (Thursday) that J (Jim) is available to tutor but Brian and Karen are not.
Assume MR =
BJK
1 0 1
M
0 1 1
T
1 0 1
0 1 0
1 1 0
W
R
F
éù
êú
êú
êú
êú
êú
êú
ëû
and MS =
12
I II III C C P
B0 1 1 0 0 1
J1 1 0 1 0 1
K0 1 0 0 1 1
éù
êú
êú
êú
ëû
(a) Interpret the above matrices with respect to the above relations.
(b) Compute
SR
M
o
, (use Boolean arithmetic) and use the matrix
SR
M
o
to determine which courses will have tutors available on which days.
(c) Multiply the above matrices using regular arithmetic. Can you interpret this result?
1
_1024390745.unknown
_1194172502.unknown
_1426926625.unknown
_1194172503.unknown
_1194172501.unknown
_1024390744.unknown
1
Week 14 Program Evaluation and Review Technique (PERT) and
Critical Path Method (CPM) Applications
Two simple, yet interesting and important applications of partial ordering relations are
the PERT and CPM techniques in job scheduling. The following description was taken
from googling PERT.
PERT is a method to analyze the involved tasks in completing a given project, especially
the time needed to complete each task, and identifying the minimum time needed to
complete the total project. PERT was developed primarily to simplify the planning and
scheduling of large and complex projects. It was developed for the U.S. Navy Special
Projects Office in 1957 to support the U.S. Navy’s Polaris nuclear submarine project.
[1]
It was able to incorporate uncertainty by making it possible to schedule a project while
not knowing precisely the details and durations of all the activities. It is more of an event-
oriented technique rather than start- and completion-oriented, and is used more in
projects where time, rather than cost, is the major factor. It is applied to very large-scale,
one-time, complex, non-routine infrastructure and Research and Development projects.
PERT is valuable to manage where multiple tasks are occurring simultaneously to reduce
redundancy
See exercise 66 in the text, section 9.6 for an example of the list of tasks needed to build
a house. Exercise 67 is also an interesting example. If we let A = {set of tasks given in
exercise 66} and define the relation R on A by : xRy iff task x precedes (is a prerequisite
task of) task y or task x = task y the Hasse diagram is as is given in the illustration in the
text.
The first step to scheduling a project is to determine the tasks that the project requires and
the order in which they must be completed. Many of the following examples are student
examples.
Note in the following examples read the diagrams from left to right.
Example 1.
The creation of a 3D video game
Tasks
1. General brainstorming (game type, setting, etc)
2. Design and implement game engine
3. Design and implement graphics engine
4. Write story
5. Design the characters
6. Design the world
7. Create 3D models
8. Create character animations
9. Voice actor casting
10. Sound recording
11. Program levels, characters, sounds, etc into game
12. Packaging
http://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique#cite_note-
0
2
1
1
3
9
5
7 8
1
0
8 12
14
18 19
Task Immediately Preceding Tasks Time required
1
1 Week
2 1 3 Months
3 1 2 Months
4 1 1 Month
5 4 2
Weeks
6 4
3 Weeks
7 5, 6 1 Month
8 7
2 Weeks
9 5 1 Week
10 9 2 Weeks
11 2, 3, 8, 10 1 Month
12 11 1 Week
Let T = { Task 1, Task 2, … , Task 11 }
Define R on T by
xRy iff x is needed for y or x = y
The Critical path seen in the figure above is 1, 4, 6, 7, 8, 11, 12. This is because the
sequence requires the most time to complete, which prevents the game from being finished.
One way that could decrease the critical path would be to design the characters and
levels as they are introduced during the story writing process. This would merge those three
tasks into one with a greatly reduced total time.
Task
1
1 Week
Task
2
12
Weeks
Task
3
8 Weeks
Task
4
4 Weeks
Task
5
2 Weeks
Task
6
3 Weeks
Task
7
4 Weeks
Task
8
2 Weeks
Task
9
1 Week
Task
10
2 Weeks
Task
11
4 Weeks
Task
12
1 Week
3
Finish
Start
2
2
2
1
0
1
1
1
1
8
8
8
7
7
3
1
Example 2. The construction of a cottage requires the performance of certain tasks. The
following table 1 lists the various tasks with their priority relationship. The start task ( )
and finish task ( ) are added, is linked to task A and is linked to task K.
Table 1
Code Of Task Duration
(Weeks)
Prerequisite tasks
A Masonry 7 –
B Carpentry for roof 3 A
C Roof 1
B
D Sanitary and
electrical
installations
8 A
E Front 2 D,
C
F Windows 1 D, C
G Garden 1 D, C
H Ceiling 3
F
J Painting 2
H
K Moving in 1 E, G, J
Let S be the set of all tasks and consider the partial order relation R defined on S
as follows: for all tasks x and y in S,
xRy x = y or x precedes y.
The minimum time required to finish this job is calculated using Project
Evaluation and Review Technique (PERT). The PERT diagram of the project is shown in
the figure 1.
Figure 1
A
D
F J H
E K
G C B
4
Finish
0
8
7
3 1
2
1
2 8
2 1
8
1
1
1
(0)
(0)
(21)
(7)
(7) (10)
(15)
(15)
(15)
(16)
(18)
(20)
In this representation, the tasks are the vertices of the graph. The length of each
task is the duration of the corresponding task. The start and finish of a task are two stages
of the project. We can define an initial stage as start and a final stage as finish and a
certain number of intermediate stages. Each stage is defined by tasks already carried out.
In the beginning milestone of the project is start stage. The start followed by task
A which is carried out in 7 weeks. After finishing stage A, we have two options. We can
start task B and task D simultaneously. Task B takes 3 weeks to finish and task D takes 8
weeks to finish the job. Task B is immediately followed by task C, which takes one week
to carry out. The minimum time required to start task C is the total time required to finish
task B and A which is 10 weeks. Task C is followed by task E. to start task E, we have to
finish C and D. C is finished in 11 weeks, and D is finished in 15 weeks, so it is very
common that we cannot start task E before finishing task D which takes 15 weeks to
carry out. Same way, we can decide the earliest time to start each task, which is shown in
Table 2. below:
Table 2
Task Earliest Start Time
Start ( ) 0
A 0
B 7
C 10
D 7
E
15
F
15
G 15
H
16
J
18
K
20
Finish ( ) 21
The above analysis shows that at least 21 weeks is required to complete the
project. The minimum duration of the project will be the length of the longest path
between the initial stage and the finish stage. This is shown in with the darker line in the
figure 2.
Figure 2
A
B
D
F
E K
G C
H J
5
If we delay any work in this path, we delay in the project finish time. That means
delay in performing any of these tasks in the path cause delay in the time required to
finish the project, and for these reason, this path is known as critical path.
The tasks outside the critical path can be delayed by certain amount of time. For
example task E is not on critical path and it is followed by task K. If we delay E by 3
week than its earliest start time, then we can start the task K as per its earliest start time
because K must be started after finishing J which takes 20 weeks. We can finish task E in
20 weeks by delaying 3 weeks. In the opposition if we delay work on the critical path, we
delay the time to complete the project. For example 3 weeks delay in task J cause 3
weeks delay to start K, and K start after 3 weeks than its earliest start time and these
cause three week delay to complete the project. Now if we finish task J earlier by one
week then we can also reach task K earlier by one week and finish it off. And finally the
overall project is also finished one week before.
Example 3.
In order to construct a house, there are many jobs that need to be done at the same
time. Certain parts of the construction must be done before others can be started. We
can not start wiring the house if the walls have not been put up, and we can not put the
walls up till the foundation had been set. Before the foundation is set, you must choose a
good plot to dig the foundation hole. However, there are certain jobs which can be done
simultaneously. While you are wiring the outlets, you can have someone do the heating
and air conditioning ducts or can have the landscaper working on the outside layout. The
partial order diagram will allow one to see how long the whole process will take.
Below, we show each task that needs to be done, and the amount of time required for that
task. The amount of time is estimated.
1. Find Plot 2 days
2.
1
Excavate land 5 days
3. Dig for foundation 3 days
4. Lay concrete foundation 5 days
5. Exterior firework 2 days
6. Exterior electrical 2 days
7. Exterior gasline 5 days
8. Supports for walls/ceiling/floor/stairs 5 days
9. Siding/Roof 3 days
10. Windows 1 days
11. Interior wiring 2 days
12. Interior plumbing 2 days
13. Heating/AC ducts 2 days
6
14. Insulation 1 day
15. Dry wall 2 days
16. Landscaping 14 days
17. Painting 2 days
18. Light Fixtures/Switches 7 hours
19. Floor Ring 2 day
20. Doors/Cabinets 1 day
21. Clean-up 1 day
The next table shows what task precedes each task. This allows us to see what tasks can
be done at the same time. If one task does not depend on the other, then those two tasks
can be done at the same time.
Task Prerequisite tasks Time
1 0 2 days
2 1 5 days
3 2 3 days
4 3 5 days
5 1,2,3,4 2 days
6 1,2,3,4 2 days
7 1,2,3,4 2 days
8 4 5 days
9 8 3 day
10 8 1 day
11 8 2 days
12 8 2 days
13 8 2 days
14 10,11,12,13 1 day
15 14 2 days
16 8 14 days
17 15 2 days
18 17 7 hours
19 17 2 days
20 19 1 day
21 20 1 day
7
Partial Order formula: x R y task x = task y or task x precedes task y
We read the following Hasse diagram from left to right to find the minimum time for the
whole process of constructing the house.
Partial Order Diagram: Construction of a House
Critical Path Method(CPM): 1,2,3,4,816,21 which is 35 days
The critical path time can be reduced if we do certain tasks differently. The time
for landscaping right now is 14 days. But if more workers are used, then the time will be
less. If pre-fabricated materials are used, then it will take less time, because less people
are needed, and less time is used in making the material. Also depending on the design
of the house, the time can be reduced or even increased. If less rooms are needed by the
Task 1
2 Days
Task 2
5 Days
Task 3
3 Days
Task 4
5 Days
Task 6
2 Days
Task 7
2 Days
Task 8
5 Days
Task 5
2 Days
Task
12
2 Days
Task
11
2 Days
Task
10
1 Day
Task
13
2 Days
Task
16
14
Days
Task
9
3 Days
Task
14
1 Day
Task
15
2 Days
Task
17
2 Days
Task
18
7
Hours
Task
19
2 Days
Task
20
1 Day
Task
21
1 Day
8
family that is living there, then it will take less time, then designing at large size home
with many rooms, and closets inside each room.
What can also reduce the time is experience of the construction workers. If the
workers are new, then they will be a bit slower, and making more mistakes which
increases the time for each task.
Example 4.. Are the partial ordering diagrams complete? Can you fill in the missing
edges?
As an application of partial order relations, I have chosen to refurbish my younger
daughter’s bedroom. This is a project that I am actually in the middle of now, but
I
decided to see how fast it would get done if I were commanding a number of
professionals. Let A={tasks}. We can define R on A by xRy iff {x=y or task x is a
prerequisite of task y}.
The job can be divided into several tasks:
1. Move all of my daughters things out.
2. Rip out doorjam from bedroom to bathroom (the bathroom is to become a
master bath).
3. Lower two electrical outlets, sheetrock holes (previous owners had a two
family with this room as a kitchen so two outlets are above where the counter used to be).
4. Frame doorway, install electrical outlet, send wires up into attic, and
sheetrock over doorway to bath.
5. Cut, sand, prepare, stain, and urethane baseboard (the old baseboard must
be destryed in taking out the door frame).
6. Attach the new outlet wires to junction box in the attic.
7 Tape, joint compound, sand, joint compound, and sand areas where new
sheetrock has been installed. Also same procedure on any cracks, etc.
8. Primer walls.
9. Install new baseboard.
10. Paint ceiling.
11. Install wall paper.
12. Clean and move furniture back in.
Some of these tasks can be done simultaneously, but most must wait for a
preceeding task to be complete. Table 1 demonstrates which task immediately precedes
another as well as the times required to complete each task.
9
Table 1.
Task Immediately Preceding Time
Task(s)
1 ½ Hour
2 1 1 Hour
3 1 4 Hours
4 2 3 Hours
5 4 6 Hours
6 4 1 Hour
7 3, 4 7 Hours
8 7 2 Hours
9 5 ½ Hour
10 8 1 Hour
11 9, 10 3 Hours
12 6, 11 ½ Hour
Table 2 displays the Hasse diagram for this relation, with the time to complete
each task included in each box.
Table 2.
To calculate the minimum time it would take to refurbish this room, we must add
the times in the diagram, adding the longest prerequisite time to the time in each box as
we go. Table 3 shows the results.
Task 6
1 Hour
Task 2
1 Hour
Task 4
3 Hours
Task 5
6 Hours
Task 9
½ Hour
Task
11
3 Hours
Task
12
½ Hour
Task 1
½ Hour
Task 3
4 Hours
Task 8
2 Hours
Task 10
1 Hour
Task 7
7 Hours
10
Table 3.
As Table 3 shows, the minimum time it would take to complete the entire job is
18 hours. What is interesting to note is that this diagram has two critical paths. To get to
task 7, both tasks 3 and 4 have 4.5 hours of prerequisite time. So the longest path in
terms of time can go from tasks 1 to 2, 4, 7, 8, 10, 11, and 12 but can also go from tasks 1
to 3, 7,8, 10, 11, and 12. These are the two critical paths
If I wanted to speed up the process, I might put an extra person on joint
compound duty and/or painting. This would have to be experimented with since some of
the times posted include drying times. Also, if too many people are on the same job, they
may simply get in each other’s way and add to times instead of reducing them.
Example 5.
Software project scheduling problem
It is Call Center software that is able to route customer information to agents. It is used
by companies that have 1-800-XXX-XXX services. This project is made of server and
client.
Call Center server is a fault-tolerant scalable server that connects clients with multiple
customer contact sources, such as calls, emails, and web collaboration sessions. It enables
thin-client applications and provides a client interface library for support access through
C, C++, Java, or COM.
The Call Center Client Interface is not limited to providing application to manage
telephone/ voice initiated interactions. It provides a broad concept of an Agent and their
interaction with multiple sources, including CTI (Computer Telephony Interface), e-mail
and web collaboration servers.
1
8
4.5
17.5
4.5
4.5
11
4.5
4.5
10
.5
4.5
Task 6
1 Hour
Task 1
½ Hour
Task 2
1 Hour
Task 4
3 Hours
Task 5
6 Hours
Task 9
½ Hour
Task
11
3 Hours
Task
12
½ Hour
Task 3
4 Hours
Task 7
7 Hours
Task 8
2 Hours
Task
10
1 Hour
.5
4.5
4.5
4.5
4.5
1
1.5
4.5
13.5
4.5
14.5
4.5
1.5
4.5
5.5
11
The project can be broken into these tasks (Table 1) in order to finish it. The start task (S)
and finish task (E) are added, S is linked to task 1 and E is linked to task 12.
Table 1
Task Description Immediately
Preceding Tasks
Time Needed to
Perform Task
Start (S) Start Task None None
1 Architect overall project S 3 weeks
2 Design Server and its
Components
1 5 weeks
3 Design Client and its
Components
1 4 weeks
4 Design Common
Components
1 4 weeks
5 Implement server and its
components
2,7 30 weeks
6 Implement client and its
components
3,7 20 weeks
7 Implement common
components
4 10 weeks
8 Test server and fix bugs 5 5 weeks
9 Test client and fix bugs 6 3 weeks
10 Implement
client interfaces
for different technologies
9 20 weeks
11 Test sever with different
client interfaces
8,10 8 weeks
12 Polish the software and
update documents and get it
ready for the customer
11 3 weeks
End (E)
End Task 12 None
12
Figure 1
In figure 1, the tasks are the vertices of the graph. The length of each task is the duration
of the corresponding task. The start and finish tasks are two stages of the project. The
initial stage is the start stage and a final stage is the finish stage.
In the beginning of the project is start stage. The start stage followed by task (1) which is
carried out in 3 weeks. After finishing task (1), we have 3 options. We can start task (2),
task (3), and task (4) simultaneously. Task (2) takes 5 weeks to finish, task (3) takes 4
weeks to finish and task (4) takes 4 weeks to finish.
In order to start task (5), we have to finish task (7) and task (2). Task (2) finishes in 8
weeks and task (7) finishes in 17 weeks, so task (5) starts after finishing task (7), which is
after 17
weeks.
In order to start task (6), we have to finish task (7) and task (3). Task (3) finishes in 7
weeks and task (7) finishes in 17 weeks, so task (6) starts after finishing task (7), which is
after 17 weeks. Task (5) and task (6) can start simultaneously.
Task (8) starts right after task (5) ends, so it starts after 47 weeks and it finishes in 5
weeks.
Task (9) starts right after task (6) ends, so it starts after 37 weeks and it finishes in 3
weeks.
Task (10) starts right after task (9) ends, so it starts after 40 weeks and it finishes in 20
weeks.
Task (11) has to wait for task (8) and task (10) end. Task (8) finishes in 52 weeks and
task (10) finishes in 60 weeks. So task (11) has to start after task (10) finishes, which is in
60 weeks and it finishes in 8 weeks.
Start
(S)
Task 2
(5)
Task 1
(3)
Task 5
(30)
Task 6
(20)
Task 3
(4)
Task 4
(4)
Task 8
(5)
Task 9
(3)
Task 7
(10)
Task 10
(20)
Task 11
(8)
Task 12
(3)
End (E)
13
Task (12) starts after task (11) ends. It starts in 68 weeks and it takes 3 weeks to finish.
Example 6.
My example PERT is based on a software development project – starting from business requirements
definition through deployment – to build a “load & rebate” system for purchasing information. It assumes
that the methodology being used calls for the completion of a users’ guide as well as user-training before
the system can be deployed to the production environment.
Task Table:
Task Preceding
Task(s)
Task Description Duration
A Business Requirements 5 days
B A Technical Requirements 2 days
C A Functional Specification – Load Application 6 days
D A Functional Specification – Rebate Application 8 days
E B Develop Technical Foundation classes
10 days
F C, E Develop Load Application 15 days
G D, E Develop Rebate Application 20 days
H F Quality Assurance (QA) Testing – Load
Application
7 days
I G Quality Assurance (QA) Testing – Rebate
Application
10 days
J C, D Prepare User Guide 4 days
K J Prepare Training Material 6 days
L H, I, K Train Users 3 days
M H, I, L Deploy System to Production Environment 1 day
(a)
B A
C
D
E
F
G
J K
H
I
L
M ω α
Finish
5
20
5
5
6
6
2
10
10
4 6
7
7
10
3
1
8
15
0
8
10
Start
14
From the above graph we can determine the earliest start time of each task and tabulate the results in the
table below. The earliest start time for a given task is the maximum of the sums of all preceding tasks.
Task Earliest Start Time
Start 0
A 0
B 5
C 5
D 5
E 7
F 11
G
17
H 26
I 37
J 13
K 17
L 47
M 50
Finish 51
The above table shows that the minimum time required to complete the tasks is 51 days.
(b)
Determining the minimum time required to complete all the tasks (above) also tells us that the critical path
is 51 days long. The diagram below shows the critical path of my project (in red and bold). This tells us
that the duration of tasks, that are on the critical path, directly affect the duration of the overall project (i.e.
extending their duration will increase the project duration while reducing their duration may reduce the
duration of the project).
(c)
Clearly, any tasks that are on the “critical” path can result in a project delay if more time is taken that
originally planned. Other tasks (that are not on the critical path) will have some element of tolerance to
overruns, but only to a point (i.e. the point up until the duration of the tasks makes it a critical task).
B A
C
D
E
F
G
J K
H
I
L
M ω α
Finish
5
20
5
5
6
6
2
10
10
4 6
7
7
10
3
1
8
15
0
8 10
15
In my example, the development of the foundation classes and rebate application (tasks E and G
respectively) makeup 30 days of programming. If two programmers were used instead of one, then it may
be possible to reduce this duration to 7 days and 15 days – thereby reducing the overall project plan
(critical path) by 8 days. The QA tasks (H and I) are also areas where project overruns could be introduced
– for example, sloppy programming may result in more time to fix bugs and retest than originally expected.
Table 2
Task Earlier Start Time
(weeks)
Start (S) 0
1 0
2 3
3 3
4 3
5 17
6 17
7 7
8 47
9 37
10 40
11 60
12 68
End (E) 71
The above analysis shows that at least 71 weeks is required to complete the project. The
minimum duration of the project will be the length of the longest path between the start stage and
the finish stage.
If we delay any work in this path, we delay the whole project. That means if we delay any of the
tasks then we cause a delay in the time required to finish the project. This path is known as
critical path.
Figure 2 shows the critical path with darker line.
Figure 2
Start
(S)
Task 2
(5)
Task 1
(3)
Task 5
(30)
Task 6
(20)
Task 3
(4)
Task
4 (4)
Task 8
(5)
Task 9
(3)
Task 7
(10)
Task 10
(20)
Task 11
(8)
Task 12
(3)
End (E)
16
The tasks that are not in critical path can be delayed by certain amount of time.
For example, if we delay task (8) by 4 weeks than its earliest start time, then we can start task
(11) as per its earliest start time because task (11) must be started after finishing task (10) which
takes 60 weeks. In the opposition, 4 weeks delay in task (10) causes 4 weeks delay to start task
(11), and task (11) starts after 4 weeks than its earliest start time and these cause 3 weeks delay
to complete the project. On the other hand, if we finish task (10) 4 weeks earlier then we can start
task (11) earlier by 4 weeks and finally the overall project is also finished 4 weeks before.
Example 7. In your notes of week 12 Project Evaluation and Review Technique (PERT)
is explained. Make up a meaningful example illustrating this process. Explain all details.
Draw the graphs involved. You should use a reasonable number of tasks.
(a) Determine the minimum time needed to complete your set of tasks.
(b) Determine the Critical Path for your example. Explain what this gives you.
Comment on your example. Which task(s) cause a delay in the project? How
would you fix the problem? Can you obtain more information out of your
example?
Project:
Title V Septic System Upgrade to my home
Tasks Prerequisites Weeks
A. send RFI to possible engineering firms, receive
responses and select engineer
– 2
B. engineer arranges for digging of test holes, perk tests,
and official oversight
A 3
C. engineer designs septic system and gets official plan
approvals
B 8
D. send RFP to possible construction contractors (contractor
& engineer must be independent by law), receive responses
and select constructor
C 2
E. constructor orders and receives settling tank and
distribution box (preformed concrete)
D 1
F. constructor orders and receives leeching bed sand
(truckloads)
D 1
G. constructor orders and receives leeching bed tubes
(perforated plastic semi-cylinders)
D 3
H. constructor orders and receives piping and tank filter
(PVC)
D 1
I. constructor excavates tank and distribution locations and
connecting trenches
D 1/5
J. constructor installs distribution box and tank E, I 1/5
17
K. constructor installs piping and tank filter H, J 1/5
L. constructor excavates leeching field D 3/5
M. constructor installs and levels leeching bed sand to level
needed for tubes
F, L 1/5
N. constructor installs leeching bed tubes G, M 1
O. constructor covers leeching bed tubes with sand,
backfills and rough grades site
K, N 3/5
P. contractor gets official inspection and approval of system O 1
Q. send RFP to possible landscape contractors, receive
responses and select landscaper
P 2
R. landscaper orders and receives loam (top soil) Q 2/5
S. landscaper finish grades site, installs loam, rakes, installs
grass seed and mulch
R 1
PERT Chart with Critical Path in red (created with Geometers Sketchpad).
Project time from start to end is 24 weeks. The leeching bed tubes ordering (3 weeks) and
installing (1 week) are the gating items in the critical path. If we could find a tube
distributor that could deliver faster we could shorten the critical path, perhaps to one
week. The installation time of the tubes could be shortened if more than one skilled
worker was assigned to the task. In fact, five lines of tubes were installed so probably five
workers could have been used, shortening task N to 1/5 of a week. But there is no need to
reduce task N below 19.6-3+1-16.4-0.6=0.6=3/5 (because then two paths would have the
same overall task time), so only increase tube installers to three people.
3
8
2
1
2 1
3
1
1/5
1/5
1/5
1/5
1/5
3/5
1/5
1/5 1
1
3/5
3/5
1
2
2/5
1
0
A (2)
B (5) C (13)
D (15)
E (16)
F (16)
G (18)
H (16)
I (15.2)
J (16.2)
K (16.4)
L (15.6)
M (16.2)
N (19)
O (19.6) P (20.6)
Q (22.6) R (23)
Start
S (24)
End (24)
18
Closures of Relations
Composition of Relations Revisited
Recall in the text the matrix of the relation S R is written as MS R and
MS R = MR MS. The purpose of the following example is to remind you of the process
and to reaffirm why it is necessary to write the product of the matrices “backwards”.
Example
1
. Assume that a University has a tutoring center and would like to determine
which subjects are available to be tutored which days of the week. Assume that the
courses to be tutored are: A = {Discrete(D), Precaculus(P),C++, Calculus(Cal)}. Assume
that there are three tutors available
B = {John(J), Melissa(M), Al(A)}. Also assume that the days that the tutoring center is
open are Monday through Friday, that is C = {M, T, W, R, F}. Assume that:
John can tutor Discrete , C++ and Calculus and he is available on M,R and F
.
Melissa can tutor Precaculus and C++ and she is available on M, W and R.
Al can tutor Discrete , Precalculus and Calculus and he is available on T, W and F.
If R is the relation from A(courses) to B(tutors) and S is the relation from B to C(days).
We want to find S R, which course are available to be tutored on which days of the
week. The easiest was of doing this is to use matrices.
Let MR = . Recall, to write this matrix prefix the first column by the elements
of A and the first row by the elements of B. You may want to do this.
1 0 1
0 1 1
1 1 0
1 0 1
⎡ ⎤
⎢ ⎥
⎢
⎢
⎢ ⎥
⎣ ⎦
⎥
⎥
⎥
⎥
⎥
⎥
Let MS = . Recall, to write this matrix prefix the first column by the
elements of B and the first row by the elements of C. You may want to do this.
1 0 0 1 1
1 0 1 1 0
0 1 1 0 1
⎡ ⎤
⎢
⎢
⎢ ⎥⎣ ⎦
So that MS R = MR MS = . The reader should prefix the first column
by the elements of A and the first row by the elements of C to determine which courses
are available for tutoring which days of the week.
1 1 1 1 1
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1
⎡ ⎤
⎢ ⎥
⎢
⎢
⎢ ⎥
⎣ ⎦
Another interesting result comes from using regular arithmetic instead of Boolean
arithmetic on the above product (MRMS).
1
MS R = MRMS = . This tells us, for example, that there are
2
tutors
available to tutor Calculus on Friday. Determine how many tutors are available to tutor
the courses on which days.
1 1 1 1 2
1 1 2 1 1
2 0 1 2 1
1 1 1 1 2
⎡ ⎤
⎢ ⎥
⎢
⎢
⎢ ⎥
⎣ ⎦
⎥
⎥
Closure Operations on Relations
In the text for section 8.4 read the first several pages to have an overview of closures in
general and the concentrate transitive closure which begins on page 547. Example 7 is a
good example to study in detail. The material below explains what transitive closure
means.
One important operation on relations is composition. This operation enabled us to
generate new relations from previously known relations. We now wish to consider the
situation of constructing a new relation R* from a previously known relation R where,
first, R*contains R and, second, R*satisfies the transitive property. Consider a telephone
network in which the main office a is connected to, and can communicate to, individuals
b and c. Both b and c can communicate to another person, d; however, assume the main
office cannot communicate with d. Assume communication is only one way, as indicated
by the following relation. This situation can be described by the relation R = {(a, b), (a,
c), (b, d), (c, d)}. We would like to change the system so that the main office a can
communicate with person d and still maintain the previous system. We, of course, want
the most economical system. This can be rephrased as follows: Find the smallest relation
R* which contains R as a subset and which is transitive. Since R* must contain R as a
subset R* must include the pairs (a, b), (a, c), (b, d), (c, d) therefore so far R* looks like
R*= {(a, b), (a, c), (b, d),(c, d), …}. Next, since both (a, b) and (b, d) are elements of R*
and R* must be transitive R*must contain (a, d) and we have R*= {(a, b), (a, c), (b, d),(c,
d), (a, d)}. The reader should check to see if any other pairs have to be included to make
it transitive. The answer is no.
Definition: Transitive Closure. Let A be a set and R be a relation on A. The
transitive closure of R, denoted by R*, is the smallest relation that contains R
as a subset and that is transitive.
Example 2. Let A = {1, 2,
3
,
4
}, and let S = {(l, 2), (2, 3), (3, 4)}
be a relation on A. This relation is called the successor relation on A since
each element is related to its successor. How do we compute S*?
By inspection we note that (1, 3) must be in S*. Let’s analyze why. This
is so since (1, 2) ∈ S and (2, 3) ∈ S, and the transitive property forces
(1,3) to be in S*. In general, it follows that if (a, b) ∈ S and (b, c)∈ S, then
(a, c) ∈ S*. This condition is exactly the membership requirement for the
pair (a, c) to be in the composition S S = S2. So every element in S2 must be
2
an element in S*. So far, S* contains at least S ∪ S2. In particular, for this
example, since S = {(l, 2), (2, 3), (3, 4)} and S2 = {(l, 3), (2, 4)}, we have
S S∪ 2 = {(l, 2), (2, 3), (3, 4), (1, 3), (2, 4)}. Is the relation S ∪ S2 transitive? Again, by
inspection, (1, 4) is not an element of S S∪ 2, but it must be an element of S* since (1, 3)
and (3, 4) are in S*. From above, (1, 3) ∈S2 and (3, 4) ∈ S, and the
composite S2 S = S produces (1, 4). This shows that S S3 3 ⊆ *. This process must be
continued until the resulting relation is transitive. If A is finite, as is true in this example,
the transitive closure will be obtained in a finite number of steps. Here,
S* = S ∪ S S 3 . 2 ∪
Note if you determined S4 or S5 or S6 etc. you would simply get S3.
Theorem If S is a relation on a set A and if #A = n, then the
transitive closure S* = S S S …. . ∪ 2 ∪ 3 nS∪
Note in the above example |A| = 4 but the transitive closure was obtained by computing
S3. So in the above theorem you need only go as far “as at most n”.
Let’s now consider the matrix analogue of the transitive closure through an example. This
will give us Theorem 3 of the text.
Example 3. Consider the relation R ={(l, 4), (2, 1), (2, 2), (2, 3),
(3, 2), (4, 3), (4, 5), (5, I)} on the set A={1, 2, 3, 4, 5}, note |A| = 5. The matrix MR of
R is
MR =
0 0 0 1 0
1 1 1 0 0
0 1 0 0 0
0 0 1 0 1
1 0 0 0 0
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
and sine R R can be computed by the matrix MR R = MRMR and since MRMR
is the product of a matrix with itself MRMR = . 2RM
2
RM =
0 0 1 0 1
1 1 1 1 0
1 1 1 0 0
1 1 0 0 0
0 0 0 1 0
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
3
RM =
1 1 0 0 0
1 1 1 1 1
1 1 1 1 0
1 1 1 1 0
0 0 0 1 0
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
3
4
RM =
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 0 0 0
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
5
RM =
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 0
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
So R* = R R∪ 2 ∪ R3 ∪ R4 R∪ 5 because |A| = 5. This equation can be expressed in
matrix form as:
MR* = MR ∨ 2RM ∨
3
RM ∨
4
RM ∨
5
RM =
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
⎡ ⎤
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥
⎢ ⎥⎣ ⎦
.
Equivalence Relations
For this topic read the definition and examples 1 through 3 and then try the
exercises.
4
