2.2.4. Column by Column Computation

Try these first

1. 1.

   How many paths exist from (0,0) to (1,1) in a grid with no obstacles?

   Hint

   Consider the two possible movements: right then up, or up then right.

2. 2.

   What is the number of paths from (0,0) to (0,0)?

   Hint

   Think about staying in the same spot.

3. 3.

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

   • 1
   • 0
   • More than 1

   Hint

   Think about the simplest path.

4. 4.

   Dynamic programming guarantees fewer calls than memoization.

   • True
   • False

   Hint

   Reflect on the efficiencies of direct vs recursive strategies.

5. 5.

   How would you compute paths in a grid of size 100x100 with random holes placed throughout?

   Hint

   Think about the memory storage needed for computations.

6. 6.

   Propose a new method to slim down the computations further in this grid-path scenario.

   Hint

   Integrate heuristic searches that rely on grid layout.