Dynamic Programming Lecture Notes

Overview of Section

• Topic: Algorithmic design and dynamic programming (DP)
• Focus: Designing polynomial time algorithms from scratch.
• Revisit: Recursive algorithms and their structure.

Key Concepts

Dynamic Programming (DP)

• A powerful algorithmic design paradigm.
• Type of recursive algorithm design.
• Allows for solving many complex problems.

Importance of Recursive Design

• Aim to write constant size code for arbitrary problem sizes (e.g., size n).
• Recursive relations help define how to break down problems into subproblems.

Sort Bot Framework

• Acronym: Helps remember steps to design recursive algorithms.
  • S: Subproblems
  • R: Relations (recurrence relations)
  • T: Topological Order
  • B: Base Case
  • O: Original Problem
  • T: Time Analysis

Steps in Dynamic Programming Design

1. Define Subproblems: Identify polynomial number of subproblems related to the main problem.
2. Recurrence Relation: Establish how to solve the main problem using solutions to subproblems.
3. Topological Order: Ensure the order of solving subproblems prevents cyclic dependencies.
4. Base Cases: Define conditions for smallest problems.
5. Original Problem: Relate back to the main problem needing a solution.
6. Time Analysis: Analyze running time of the algorithm.

Example: Merge Sort

• Subproblems: Sorting subarrays of an array.
• Recurrence Relation: Merge two sorted arrays.
• Base Case: Sorting an empty or single-element array.
• Time Complexity: O(n log n).

Example: Fibonacci Numbers

• Subproblems: Compute the nth Fibonacci number.
• Recursive Relation: F(n) = F(n-1) + F(n-2).
• Base Cases: F(1) = 1, F(2) = 1.
• Issue: Naive recursion leads to exponential time due to repeated calculations.

Memoization Technique

• Store results of subproblems to avoid redundant calculations.
• Turns exponential time complexity into linear time O(n).

Example: DAG Shortest Paths

• Subproblems: Compute shortest path weights from a single source vertex to all vertices.
• Relation: Shortest path to vertex v is minimum of shortest paths to all incoming vertices (u) plus edge weight.
• Topological Order: Use topological sorting of the graph to ensure proper order of computation.
• Time Complexity: O(v + e) where v = vertices and e = edges.

Application: Bowling Problem

• Problem Definition: Maximize score when bowling at pins in a line.
• Subproblems: Define b(i) as maximum score starting from pin i.
• Recurrence Relation: Evaluate options for hitting pins: skip, hit alone, hit in pairs.
• Base Case: b(n) = 0 (no pins left).
• Time Complexity: O(n).

Conclusion

• Dynamic programming optimizes problems with overlapping subproblems and optimal substructure.
• Understanding how to break problems into subproblems and design relations is key to creating efficient algorithms.
• The next lectures will explore more complex examples of dynamic programming.