2.2.5. Topological Sorting

Try these first

1. 1.

   What is the total number of paths from (0,0) to (1,1) in a 2x2 grid?

   Hint

   Consider the different orders of movements.

2. 2.

   If a hole exists at (1,1), how many paths are available to (2,2)?

   Hint

   No hint provided

3. 3.

   How many paths are there from (0,0) to (2,2) in an unobstructed grid?

   • 2
   • 4
   • 6

   Hint

   Think about the different sequences of right and down movements.

4. 4.

   True or False: Dynamic programming requires a directed acyclic graph to visualize dependencies.

   • True
   • False

   Hint

   Recall how dependencies are structured.

5. 5.

   Given a grid with dimensions 6x6 and holes at (2,3) and (4,5), calculate how many distinct paths exist from (0,0) to (5,5).

   Hint

   Start from (0,0) and fill row by row or column by column.

6. 6.

   Explain under what conditions memoization is preferable to dynamic programming.

   Hint

   Consider the efficiency of recursive vs iterative solutions.