2.1.1. Paths to (i,j)

Try these first

1. 1.

   How do you calculate the number of paths to (2,1) from (0,0)?

   Hint

   Count the ways to get to the first point and then to the second.

2. 2.

   What is the value of paths(0,0)?

   Hint

   Think about staying in one spot.

3. 3.

   What is the key method used to calculate paths(i,j) in a grid?

   • By moving only right
   • By moving only up
   • From neighbors on left or below

   Hint

   Think about the movement options on a grid.

4. 4.

   True or False: If there is a hole at (2,1), paths(2,1) would be zero.

   • True
   • False

   Hint

   Consider how holes affect calculations.

5. 5.

   Design a 5x5 grid with multiple holes. Calculate paths to (4,4) considering obstacles dynamically and using memoization. Discuss the efficiencies and pitfalls of each method.

   Hint

   Document steps as you fill in the grid, then analyze results.

6. 6.

   Create a real-life application for pathfinding similar to this grid setup. How would obstacles affect routing?

   Hint

   Think algorithms used in GPS applications or logistics.