Coding Assignment 3
Topological Sorting
Directions:
Submit your assignment as a single Jupter notebook filing using the naming scheme
as follows: yourWSUID CA3.
You should use Pyhon scripts, LaTex, or Markdown as necessary to complete each
question.
Questions:
1. (15 points) During lecture we discussed the Topological Sorting algorithm and situations
in which it might be used. Use the pseudocode below to write a script that performs a
topological sorting of a partially ordered set.
Algorithm 0.1 (Topological Sorting).
procedure topological sorting ((S, ≼): finite poset)
k := 1
while S ̸= ∅
ak := a minimal element of S { such that an element exists by the Lemma }
S := S − {ak}
k := k + 1
return a1, a2, . . . , an ({a1, a2, . . . , an} is a compatible total ordering of S.)
2. (15 points) Expanding on this idea, write a script that will take a partial ordering on a
finite set, constructs the covering relation, i.e. the Hasse Diagram, in adjacency matrix
form, and then applies your topological sorting script to find a compatible total ordering.
1
3. (20 points) In project management, there are two algorithms/tools often used in conjunction with one another to schedule tasks involved in completing a project. These
methods are known as Program Evaluation and Review Technique (PERT) and
Critical Path Method (CPM). From Wikipedia:
PERT and CPM are complementary tools, because ”CPM employs one time
estimation and one cost estimation for each activity; PERT may utilize three
time estimates (optimistic, expected, and pessimistic) and no costs for each
activity. Although these are distinct differences, the term PERT is applied
increasingly to all critical path scheduling.”
Below you will find some data describing a set of activities, their respective precedence,
and some time estimates for completion, where o is optimistic time, m is normal or most
likely time, and p is pessimistic time. Expected time is then calculated as a weighted
average of these by (o + 4m + p)/6.
Activity Predecessor Time estimates Expected time Opt. (o) Normal
(m)
Pess. (p)
A – 2 4 6 4.00
B – 3 5 9 5.33
C A 4 5 7 5.17
D A 4 6 10 6.33
E B,C 4 5 7 5.17
F D 3 4 8 4.50
G E 3 5 8 5.17
As we have not discussed weighted graphs or shortest-path problems yet, please complete
the following:
(a) Construct the precedence relation and represent it as a graph for the given set of
activities. Plot this graph.
(b) Construct the adjacency matrix for the precedence relation and display this matrix.
(c) Use your topological sorting script to find a compatible total ordering for the precedence relation.
(d) What other information should we consider if we wanted to optimize the schedule
for the tasks given? What would the “worst case scenario” be?
2
