Scribd
Upload
18 views

Dynamic_programming

Uploaded by

tharanrr3
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
18 views

Dynamic_programming

Uploaded by

tharanrr3
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 16

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

You might also like