24.1.5. Algorithm Complexity

Try these first

1. 1.

   Define in-degree.

   Hint

   Think about how many arrows point at a specific point.

2. 2.

   What is one method to find out which vertex to process in topological sort?

   Hint

   What means you don't need to wait for anything else to start working?

3. 3.

   What is the time complexity using an adjacency matrix for topological sorting?

   • O(n)
   • O(n^2)
   • O(n + m)

   Hint

   Think about the size of the matrix.

4. 4.

   True or False: In topological sorting, a vertex with in-degree 0 can be processed immediately.

   • True
   • False

   Hint

   Consider what in-degree indicates during processing.

5. 5.

   Given a directed graph represented by edges: {(A, B), (B, C), (C, D), (A, D)}, implement a topological sorting algorithm using an adjacency list.

   Hint

   Consider how you will maintain the list as you process each vertex.

6. 6.

   In a project management scenario with tasks represented as a directed graph, design a strategy to implement topological sorting to schedule tasks while minimizing dependencies.

   Hint

   Think about how dependencies affect the order of execution.