[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 03:56:43 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Graphs:   Directed Acyclic G's (DAGs):   Introduction



Examples of partial orders, i.e. potential DAGs:

  1. sub-tasks of a project and "must finish before"

  2. subjects for a degree and "is a prerequisite for"

  3. people and "is a descendant of"

  4. sets and "is a subset of"

  5. other: you think of some: [___________________________]

DAG example:

Simplified (!) prerequisites for Computer Science, Monash University, Australia, 2000:

CSE1303 (Comp Sci): CSE1301

CSE2303 (Formal Methods I): CSE1301, MAT1830, MAT1841

CSE2304 (Alg + D S): CSE1303, MAT1830, MAT1841

CSE2302 (Op' Sys'): CSE1303, MAT1830, MAT1841

CSE2305 (OOP): CSE1303, MAT1830, MAT1841

CSE3301 (Project): CSE2304

CSE3305 (Formal Methods II): CSE2303, CSE2304
[lecturer: draw the graph; class: take notes!]   Do NOT take this as course advice!

A Topological-Sort of a DAG

e.g. gives you an ordering of subjects for taking a degree, one subject at a time, while obeying prerequisite rules.

[lecturer: run the demo'; class: draw DAGs, take notes!]
procedure Depth_First(i :Vertex) // Note similarities
   if not visited[i] then        // with Tree traversals.
      visited[i] := true;
      for all edge <i,j>         // j must follow i in top'-sort
      end for;
      save(i)                    // record or process Vertex i
   end if
end Depth_First;

for all i :Vertex        // initialise visited[]; been nowhere!
   visited[i] := false
end for;

for all i :Vertex        // try all possible starting points
end for -- [class: run it!]

Critical Path Analysis of a DAG

Critical path analysis of a DAG,   two equivalent strategies:

1. How soon (after start) can a sub_task finish?

2. How late (before dead-line) can a sub_task begin?

Critical path analysis of a DAG:
traverse vertex: i.e. "depth"- (pre-req'-) first traversal.   Throughout, record the lastest end time seen.
[lecturer: do examples; class: draw diagrams, take notes!]


Graphs:  Directed Acyclic Graphs (DAGs):  Summary

Revise sub-string searching and prepare suffix trees.
© L.Allison, Sunday, 28-Nov-2021 03:56:43 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/18DAG.shtml
Computer Science, Software Engineering, Science (Computer Science).