23.2.8. Algorithm for Topological Sorting

Try these first

1. 1.

   What does a Directed Acyclic Graph represent?

   Hint

   Think about the directionality and presence of cycles.

2. 2.

   Define in-degree.

   Hint

   Consider incoming connections to a task.

3. 3.

   Which of the following is true about DAGs?

   • They have cycles
   • They allow topological sorting
   • They are undirected

   Hint

   Recall the definitions of DAGs.

4. 4.

   True or False: A topological sort can be performed on any graph.

   • True
   • False

   Hint

   Consider the requirement of the directed edges and cycles.

5. 5.

   In a DAG representing course prerequisites, you have the following courses: A (Math), B (Physics), C (Programming), D (Data Structures). If Math is required for Physics, and Programming is necessary for Data Structures, what is a valid topological ordering of courses?

   Hint

   Ensure prerequisites are ordered before dependent courses.

6. 6.

   Create and explain a DAG for software development, identifying at least six tasks and their dependencies.

   Hint

   Think about the typical software development lifecycle and dependencies.