Questions
3 questions in typical university papers
Difficulty
Medium
Importance
High yield for algorithm design and logic papers
Overview
Dynamic Programming (DP) and Greedy algorithms are fundamental optimization techniques used to solve complex problems by breaking them into simpler sub-problems. Understanding these is crucial for university exams, as they test your ability to distinguish between local optimality and global efficiency.
Memoization vs Tabulation
These are the two primary approaches to implement Dynamic Programming. Memoization is a top-down technique where results are stored recursively as they are computed, while Tabulation is a bottom-up approach that fills a table iteratively.
- Memoization uses recursion (top-down)
- Tabulation uses iteration (bottom-up)
- Memoization only computes required sub-problems
- Tabulation computes all sub-problems
- Tabulation avoids recursion stack overhead
Classic DP Problems
These problems represent the standard patterns of DP applications, usually involving overlapping sub-problems and optimal substructure. Mastery of these patterns is essential for deriving solutions to related exam questions.
- 0/1 Knapsack Problem
- Longest Common Subsequence (LCS)
- Matrix Chain Multiplication
- Optimal Binary Search Tree
- Fibonacci Series via DP
Greedy Algorithm Design
Greedy algorithms make a series of locally optimal choices at each step with the hope of finding the global optimum. Unlike DP, they do not reconsider past decisions, making them efficient but not always correct for every problem type.
- Greedy Choice Property
- Optimal Substructure Property
- Fractional Knapsack (Greedy works)
- Huffman Coding
- Dijkstra's Shortest Path Algorithm
Formula Sheet
DP[i] = min(DP[i-1], DP[i-2]) + cost
LCS(i, j) = 1 + LCS(i-1, j-1) if X[i] == Y[j]
Knapsack Capacity: W >= w[i]
Exam Tip
Always write the recurrence relation first for DP questions, as partial marks are heavily weighted toward the logic of the transition state.
Common Mistakes
- Confusing the Greedy strategy with DP, specifically applying Greedy to the 0/1 Knapsack problem where it fails.
- Neglecting to mention the state transition relation (recurrence relation) in descriptive exam answers.
- Overlooking base cases in recursive DP solutions leading to infinite loops.
More Revision Notes
Ready to test yourself?
Play topic-wise Dynamic Programming & Greedy questions in Aspirant Arcade — gamified MCQ practice.
Download Free