15. Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling

Erik Demaine introduces a new section of the course focusing on algorithmic design, particularly dynamic programming, a recursive algorithmic design paradigm. This approach allows solving complex problems by writing constant-sized code, independent of problem size, through recursion or loops. The class uses proof-by-induction and subproblem graphs to discuss algorithm design, introducing an acronym SRTBOT (Sub-problems, Relations, Topological order, Base case, Original problem, Time) to help remember the steps in recursive algorithm design. Dynamic programming builds on this with memoization, reusing previous work.

To avoid infinite loops in recursive algorithm calls, ensure the dependencies between subproblems are acyclic, which involves specifying a topological order. Base cases solve recursive structures, and the goal is to solve the original problem using subproblems. The course will explore dynamic programming through various examples, starting with illustrating via merge sort, though it's a divide and conquer algorithm. Merge sort involves sorting sub-arrays and using recurrence relations to solve problems iteratively, maintaining a topological order and base case while sticking to known recurrence solutions like the one in merge sort for analysis.

Illustrating recursion on Fibonacci numbers through a toy problem to introduce memoization, a key concept in dynamic programming. The Fibonacci calculation using recursion without memoization results in exponential time complexity due to repeated calculations. With memoization, results of subproblems are cached and reused, drastically improving efficiency to linear time by reducing redundant calculations. Explaining through drawings and examples, Demaine emphasizes rewriting recursions to check cache first before proceeding and how this significantly cuts down computation time and complexity.

Detailed explanation of leveraging memoization with Fibonacci recursion to optimize from exponential to linear time solutions demonstrates the utility of this technique in reducing redundant calculations. The memoization technique ensures that each subproblem is only solved once, providing significant computational savings. Discussion on how traditional assumptions about arithmetic operations being free in typical algorithm analysis are adjusted, emphasizing polynomial growth versus exponential along with explorations into merge sort's complexities, confirming it's an inefficient use of memoization.

Illustrating the inadequate outcome of applying recursive approaches to different problem types like merge sort, emphasizing the utility and power of dynamic programming when used appropriately. Introducing the DAG (Directed Acyclic Graph) shortest paths problem, a distinct case of reuse where algorithmic insights can bridge dynamic programming concepts applied in efficient, non-recursive manners. Highlighting dynamic programming's efficiency through examples like solving DAG shortest paths by leveraging direct edge calculations and recursion to deliver improved time complexities compared to naive methods.

Describing dynamic programming interpretations as recursive computations with memoization, hinting at how algorithms recursively employ depth-first search structures inherently due to problem type and constraints. Through DAG shortest paths, Demaine articulates how dynamic programming captures implicit explorations, solving computational problems by systematically breaking down dependencies between given graph nodes, emphasizing the automated topological ordering ensured through memoization, effectively converging memory and computation affordably.

Introducing bowling as a novel computational problem to showcase dynamic programming in practice. With constraints resembling real-life problems, this example is devised to demonstrate computational efficiency, utilizing dynamic programming principles. Using simple rules and adding scoring functions, the bowling challenge is constructed as a fun analogy to algorithmic problem-solving. Demaine explains setup, criteria, and scoring, presenting the problem as a sequential challenge, which is crucial for understanding the practicality of algorithmic concepts applied in sequence analysis.

Demaine introduces a new unique problem setup, playing an ancient-like bowling game where values are attached to each pin, with the emphasis on maximizing score through strategic gameplay, providing an engaging classroom challenge to solve using dynamic programming. Bowling serves as a metaphorical ground for applying ideas about sequence influence and impact of actions, reflecting on problem-solving approaches that heavily rely on strategic considerations of operations order and possible outcomes, thus pushing attention towards maximizing expected outcomes using sequence logic.

He presents SRTBOT methodology applied to bowling problem-solving. By breaking down pins into sequential sub-problems and evaluating various solutions pathways, the key concepts of dynamic programming come into play. Demaine outlines how suffixes of sequences can serve as essential sub-problems in dynamic problem formulations. Through strategic evaluation of each pin's possible interactions and the subsequent effect on the configuration, outcomes are optimized using local brute force creatively bounded by predefined subproblem scopes, avoiding exponential complexity growth.

The explanation extends to implementing dynamic programming solutions both recursively and iteratively (bottom-up), highlighting the procedural transformation from theoretical model to practical coding. Through structured conditional logic, explicit ordering, and simplicity in mathematical expressions (like max/min functions), algorithmic joys are shared, linking dynamic model adjustments and real-world coding habits (e.g., bottom-up implementation mimicking memoization). Demaine emphasizes computational thinking where problems are visualized as sequence-bound, favoring early breakdowns and task automation.