Design and Analysis of Algorithms · Unit 5 · 8 hrs
Dynamic Programming
Exam-focused notes for Dynamic Programming (Design and Analysis of Algorithms, CSC325): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming, Elements of DP Strategy
- DP Algorithms: Matrix Chain Multiplication, String Editing, Zero-One Knapsack Problem, Floyd Warshwall Algorithm, Travelling Salesman Problem and their Analysis
- Memoization Strategy, Dynamic Programming vs Memoization
DP Algorithms
Distinguish between dynamic programming and memorization. Parenthesize the matrices A(30 × 1), B(1 × 40), C(40 × 10) and A(10 × 15), for computing matrix multiplication using dynamic programming.[10]
Feature Dynamic Programming Memoization --------- Approach Bottom-up Top-down Implementation Iterative (fills a table) Recursive with a cache Sub-problems solved All sub-problems computed Only the sub-problems actually needed Overhead No recursion overhead ...
Full solved answer →How does 0/1 Knapsack problem differ from fractional one? Find the minimum vertex cover in the following graph. [5+0]
- Mark distribution: [5 + 0] - Part 1 (difference between 0/1 and fractional knapsack): 5 marks - Part 2 (minimum vertex cover of "the following graph"): 0 marks - Missing data: The graph referenced in Part 2 ("the following graph") is NOT included in the q...
Full solved answer →Differentiate between Dynamic Programming and Memoization. Compute the Shortest Path Between Every Pair in the Following Graphs Using Floyd Warshall Algorithm. [10]
Aspect Dynamic Programming Memoization --------- Approach Bottom-up Top-down Implementation Iterative (loops) Recursive with caching Order of solving Solves smaller subproblems first, builds up Breaks main problem down recursively Table filling Fills entire...
Full solved answer →Define order statistics problem. Find the edit distance between 'cat' and 'car' using dynamic programming. [5]
--- Definition: Given a set (or array) $A$ of $n$ elements drawn from a totally ordered set, the $i$-th order statistic is the $i$-th smallest element of $A$. - Input: An array $A$ of $n$ elements and an integer $i$ where $1 \le i \le n$. - Output: The elem...
Full solved answer →Matrix Chain Multiplication
Matrix Index Size --------------------- A 1 $5 \times 10$ B 2 $10 \times 15$ C 3 $15 \times 20$ D 4 $20 \times 30$ Number of matrices: $n = 4$ Dimension array: $$p = [p0, p1, p2, p3, p4] = [5, 10, 15, 20, 30]$$ (Note: the question text repeats "ABCD" three ...
Full solved answer →Find the edit distance between the string "ARTIFICIAL" and "NATURAL" Using dynamic programming. [5]
- String A = "ARTIFICIAL", length $m = 10$: A-R-T-I-F-I-C-I-A-L - String B = "NATURAL", length $n = 7$: N-A-T-U-R-A-L - Operations allowed: insertion, deletion, substitution (each cost 1). $$dp[i][j] = \begin{cases} i & j = 0 \\ j & i = 0 \\ dp[i-1][j-1] & ...
Full solved answer →Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming, Elements of DP Strategy
Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order $2, 3, 4, 2, 5$. [10]
Aspect Dynamic Programming Greedy Strategy --------------------------------------------- Global optimality Guarantees a globally optimal solution by examining all relevant subproblem combinations May settle for a locally optimal choice that is not globally ...
Full solved answer →Explain in brief about the Dynamic Programming Approach for algorithm design. How it differs with recursion? Explain the algorithm for solving the 0/1 Knapsack problem using the dynamic programming approach and explain its complexity.[10]
Dynamic Programming is a method for solving complex problems by breaking them down into simpler overlapping subproblems, solving each subproblem only once, and storing the results (in a table/array) to avoid redundant computation. DP is applicable when a pr...
Full solved answer →What do you mean by Dynamic programming strategy? Explain the element of DP. [5]
Dynamic Programming (DP) is an algorithm design strategy used to solve optimization problems by breaking them down into smaller overlapping subproblems, solving each subproblem only once, and storing the results to avoid redundant computation. It finds the ...
Full solved answer →Memoization Strategy, Dynamic Programming vs Memoization
What do you mean by memorization strategy? Compare memorization with dynamic programming. [5]
Memoization is a technique used to "remember" (store) the result of a computation so that the next time the same sub-problem is encountered, the stored result is reused directly instead of recomputing it, thereby saving time. With memoization, the algorithm...
Full solved answer →Make Unit 5 stick
Practice CSC325 with flashcards & quizzes