Lecture on Dynamic Programming

Introduction

• Dynamic Programming (DP) is a powerful algorithm design technique.
• The next four lectures will cover DP, focusing on optimization problems.
• DP is useful for solving problems like shortest paths and more, often turning exponential time solutions into polynomial time.
• DP can be seen as a careful brute-force approach.

Why is it Called Dynamic Programming?

• Named by Richard Bellman to sound appealing and avoid negative connotations associated with research at the RAND corporation.

Core Concepts of Dynamic Programming

• Subproblems: Decompose a problem into smaller, manageable subproblems.
• Memoization: Store solutions to subproblems to avoid redundant calculations.
• Recursion: Use recursive functions to solve problems, but enhance them with memoization.
• Guessing: Try all possible solutions for subproblems and choose the best one.

Example: Fibonacci Numbers

• Naive Recursive Approach: Inefficient, exponential time due to repeated calculations.
• Memoization: Store previously calculated results to achieve linear time complexity.
  • Create a dictionary to store Fibonacci values.
  • Check if a value is already computed before calculating it.
• Bottom-Up Approach: Iteratively calculate Fibonacci numbers, storing only needed values to optimize space usage.

Key Idea in Dynamic Programming

• Running time = Number of subproblems * Time per subproblem.
• Dynamic programming is recursion plus memoization (and guessing).

Application: Shortest Paths

Single Source Shortest Paths

• Recursive Algorithm: Compute shortest paths by considering all possible last edges to a vertex.
• Memoization: Makes the recursive algorithm efficient for dags (acyclic graphs).
  • Running time for dags: V + E (number of vertices + number of edges).
• Challenges with Cycles: Infinite recursion occurs in graphs with cycles.

Handling Cycles

• Layered Graph Approach: Transform the graph into a layered, acyclic version to handle cycles.
• Delta Definition: Define subproblems as shortest paths using at most K edges.
  • Delta subk of (S, V) is the shortest path from S to V using at most K edges.

Conclusion

• Dynamic Programming is a versatile tool for algorithm design.
• It involves breaking down problems, memorizing solutions, and trying different approaches systematically.
• In upcoming lectures, more complex and interesting applications of DP will be explored.