23.8. Computational Challenges

Try these first

1. 1.

   Define factorial using inductive definitions.

   Hint

   What is the base case for factorial?

2. 2.

   What does the term 'memoization' mean?

   Hint

   Think of it as a cheat sheet.

3. 3.

   What is dynamic programming?

   • A method for solving equations
   • A programming language
   • A technique for solving complex problems efficiently

   Hint

   Think about the best way to tackle difficult problems.

4. 4.

   True or False: Memoization helps in reducing the computation time by storing previous function results.

   • True
   • False

   Hint

   Does caching sounds like a time-saving strategy to you?

5. 5.

   Given a set of jobs each with a start time, finish time, and weight, outline an algorithm to maximize total weight for the interval scheduling problem.

   Hint

   How would you store previously calculated weights to optimize your solution?

6. 6.

   Create a recursive solution for calculating the nth Fibonacci number using inductive definitions and then improve it using dynamic programming.

   Hint

   Consider how each Fibonacci number builds off the previous two.