25.1.3. Example with Courses and Prerequisites

Try these first

1. 1.

   Define a Directed Acyclic Graph (DAG).

   Hint

   Think about paths that don't loop back.

2. 2.

   What does topological sorting achieve?

   Hint

   Consider the impact of prerequisites on ordering.

3. 3.

   What defines a Directed Acyclic Graph (DAG)?

   • Contains cycles
   • No cycles
   • Has only one vertex

   Hint

   Focus on the structure - can you loop back?

4. 4.

   True or False: Topological sorting can be applied to any graph.

   • True
   • False

   Hint

   What about cycles in a graph?

5. 5.

   Consider a university with courses A, B, C, D, where A -> B, A -> C, and C -> D. If A must be taken before B and C, how many semesters will be required to complete all courses?

   Hint

   Draw the DAG and analyze the dependencies.

6. 6.

   In a given DAG of courses represented by nodes with varying indegrees, propose an algorithm to optimally calculate the longest path.

   Hint

   Think about the maximum values from what you already know.