2.2.1. DAG Structure of Dependencies

Try these first

1. 1.

   How many ways can you reach (1,1) from (0,0)?

   Hint

   Think about the paths you can take.

2. 2.

   If (2,2) has a hole, how many paths lead to it?

   Hint

   What happens if a hole blocks the way?

3. 3.

   How many paths exist to (0, 0)?

   • 0
   • 1
   • 2

   Hint

   Consider the base case.

4. 4.

   True or False: Dynamic programming always yields fewer calculations compared to memoization.

   • True
   • False

   Hint

   Think about how each technique processes subproblems.

5. 5.

   Given a 5x5 grid with holes at (1,2), (2,2), and (3,3), calculate the total unique paths from (0,0) to (4,4).

   Hint

   Construct a dynamic programming table or visualize the grid.

6. 6.

   Design a function to compute paths in an arbitrary sized grid with variable hole placements. How does the algorithm shift with each new hole introduced?

   Hint

   Consider how the grid values propagate.