EC9600: APPLIED
ALGORITHMS
DYNAMIC
PROGRAMMI
NG
2020/E/010
2020/E/041
2020/E/155
CONTENTS
• Introduction
• Problem and Importance
• Key Characteristics
• Importance in Computing
• Variants and Optimization
• Some Common Problems
• Fibonacci Numbers
• Longest Common Subsequence
• 0/1 Knapsack Problem
• Pros and Cons
• Q&A
Introduction
Historical Context
•Developed by Richard Bellman in 1953
•Named to sound impressive for government funding
•Original focus: Mathematical optimization problems
•Evolution into fundamental computer science concept
Creator's Background
•Richard Bellman (1920-1984)
•RAND Corporation researcher
•Major contributions to mathematics and computer science
•Received IEEE Medal of Honor in 1979
Problem and Importance
Core Problem
Dynamic Programming solves complex problems by:
•Break the problem down into simpler subproblems
• Storing solutions to subproblems to avoid recomputation
through Memoization.
• Optimizing the sub problems to get the optimum solution
systematically
Key Characteristics
1.Optimal Substructure
2.Overlapping Subproblems
3.Memoization
Importance in Computing
• Enables solving otherwise intractable problems
efficiently
•Reduces time complexity from exponential to
polynomial in many cases
•Critical for optimization problems in various
domains
Variants and Optimizations
• Variants
• Top –Down (Memoization)
- Recursion with catching results
• Bottom Up (Tabulation)
- Iterative solutions using a table
• Optimizations
- Space Optimization – Using 2 variables instead of an
entire table
Eg:- Fibonnacci with O(1) space
- State Compression – Reducing states in multi-
dimensional problems.
•Impact – Reduces runtime and space complexity
1. Fibonacci Numbers
Basic Implementation Optimized Version (Memoization)
1. Fibonacci Numbers
Space-Optimized Version Real-World Applications
(Tabulation)
1.Financial Market Analysis
1.Goldman Sachs: Market prediction
models
2.BlackRock: Pattern recognition in
trading
2.Natural Growth Patterns
1.Biological research institutions
2.Population growth modeling
2. Longest Common Subsequence (LCS)
Basic Implementation Optimized Version (Dynamic
Programming)
2. Longest Common Subsequence (LCS)
Space-Optimized Version
Real-World Applications
1.Bioinformatics
• Illumina: DNA sequence alignment
• 23andMe: Genetic similarity analysis
2.Version Control Systems
• GitHub: File diff algorithms
• GitLab: Code merge tools
3. 0/1 Knapsack Problem
Basic Implementation Optimized Version
3. 0/1 Knapsack Problem
Space-Optimized Version Real-World Applications
1.Logistics & Shipping
• Amazon: Warehouse packing
optimization
• FedEx: Cargo loading optimization
2. Resource Allocation
• Microsoft Azure: Cloud resource
allocation
• AWS: Container deployment
optimization
Pros and Cons
Advantages
Efficiency: Reduces time complexity significantly
Example: Fibonacci from O(2ⁿ) to O(n)
Optimality: Guarantees optimal solution
Versatility: Applicable to many problem types
Systematic: Provides structured approach to problem-solving
Limitations
Memory Requirements: Can need significant space
Example: 2D DP table for sequence alignment
Problem Structure: Requires optimal substructure
Implementation Complexity: Can be tricky to get right
State Space: May grow exponentially with problem dimensions
Pros and Cons
Thank
You
Q&A
