25.1.9. Complexity Analysis

Try these first

1. 1.

   What does it mean for a graph to be a Directed Acyclic Graph?

   Hint

   Think about cycles in graphs.

2. 2.

   Define topological sorting.

   Hint

   Consider how to order tasks.

3. 3.

   What is a Directed Acyclic Graph?

   • A graph with cycles
   • A graph with directed edges and no cycles
   • A disconnected graph

   Hint

   Focus on the definition of a DAG.

4. 4.

   True or False: The longest path in a DAG represents the simplest tasks.

   • True
   • False

   Hint

   Consider what the longest path implies.

5. 5.

   Construct a DAG for five tasks where task E depends on tasks C and D, while task D depends on B and A. Determine the longest path.

   Hint

   Focus on the dependencies outlined in the DAG.

6. 6.

   Given a course structure with prerequisites and a scheduled semester plan, identify if the schedule allows completion in the minimum number of semesters.

   Hint

   Check for any circular dependencies.