25.1. DAGs: Longest Paths

Try these first

1. 1.

   What is a directed acyclic graph?

   Hint

   Think about graphs that allow paths but not loops.

2. 2.

   What do we understand by the term 'indegree'?

   Hint

   Consider how many graphs point towards a particular node.

3. 3.

   What does a Directed Acyclic Graph (DAG) not contain?

   • Cycles
   • Multiple edges
   • Disconnected vertices

   Hint

   Think about the fact that paths need to respect a starting point.

4. 4.

   The process of arranging the vertices in a DAG respecting dependencies is called?

   • Topological Sorting
   • Graph Traversal
   • Breadth-First Search

   Hint

   Remember it’s about respecting a sequence of tasks.

5. 5.

   Given a set of courses represented as a DAG, compute the longest path and determine the minimum number of semesters needed. The courses are: 1, 2 (no prereqs), 3 (depends on 1), 4 (depends on 1), 5 (depends on 1), 6 (depends on 3), 7 (depends on 6), 8 (depends on 2, 4, 5, and 7).

   Hint

   Draw the graph and label dependencies step by step.

6. 6.

   Create a DAG to represent project tasks where tasks A, B must be done before task C; task A also leads to task D; and task D leads to task E. Find the longest path.

   Hint

   Map out all tasks and visualize their connections to understand dependencies.