Greedy Algorithms and Dynamic Programming
Date: December 24, 2020
Conducted by: Utkarsh, Harsh, Hemant
Agenda
-
Greedy
- Thinking greedily
- Greedy choice property
- Optimal substructure
- Problem discussion and Applications
- Thinking greedily
-
Dynamic Programming
- Introduction
- Solving a Problem
- Propertites of DP problems
- Optimal Substructure
- Overlapping Subproblems
- States and Transitions
- Memoization and Tabulation
- Some Standard Problems
- 0-1 Knapsack Problem
- Conclusion
Resources
- Greedy algorithms Video - Google Drive
- DP basics Slides - Google Slides
- Implementation for that AtCoder Problem:
- Implementation for the Knapsack problem: link