Grahs in Aplgorithms applications

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 con- junction 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 prece- dence 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