Algorithms

NPTEL / GATE CS / UGC NET Core Subject Key Exam Questions: 0/1 Knapsack recurrence and table filling, LCS length recurrence ($O(mn)$), Matrix Chain Multiplication parenthesization ($O(n^3)$), Coin Change variations, and Space Optimization techniques.

1. Prerequisites & What You Should Know#

Before mastering Dynamic Programming, ensure you understand:

• Recursion Trees & Redundant Work: Being able to trace a recursive call stack and spot repeated subproblem evaluations.
• DAG (Directed Acyclic Graph) Topological Ordering: Every DP problem represents a topological sort over a DAG of dependent states!
• State Representation: Defining what parameters uniquely identify a subproblem (e.g., dp[i][w] = max value using first $i$ items with capacity $w$).
• Mathematical Induction: Showing that if smaller states are optimal, the transition function preserves optimality for larger states.

2. Conceptual Intuition: The Fibonacci Tragedy & The Sticky Note#

Naive Recursive Fibonacci: fib(5)
                           fib(5)
                       /           \
                  fib(4)            fib(3)
                 /      \          /      \
             fib(3)    fib(2)    fib(2)   fib(1)
            /     \     /   \     /   \
        fib(2)  fib(1) f(1) f(0) f(1) f(0)
        /   \
      f(1)  f(0)

Notice: fib(3) is recomputed 2 times!
        fib(2) is recomputed 3 times!
Total calls grow exponentially as O(2^n) = O(1.618^n)!
For n = 50, naive recursion takes ~1.12 * 10^15 operations (years of compute).

The Sticky Note (Memoization) Principle#

"Those who cannot remember the past are condemned to repeat it." — George Santayana (Adapted by Richard Bellman)

Whenever you compute an answer to a subproblem for the first time, write it down on a sticky note (lookup table / array). Before performing any recursive calculation, first check if you already have a sticky note for that exact input. If so, return it in $O(1)$ constant time!

This collapses the entire exponential tree down into a linear chain of $n$ unique states: $O(n)$ time!

3. The Two Golden Rules of Dynamic Programming#

A problem can be solved using Dynamic Programming if and only if it satisfies:

1. Overlapping Subproblems: A recursive algorithm visits the exact same subproblems over and over, rather than generating brand-new subproblems at every step (which occurs in Divide & Conquer).
2. Optimal Substructure: An optimal solution to the global problem can be constructed by combining the optimal solutions of its subproblems.

4. Memoization (Top-Down) vs Tabulation (Bottom-Up)#

Top-Down (Memoization):
[Main Problem] -> Needs Subproblem A & B -> Recurse downwards -> Base cases reached -> Store in cache & return up

Bottom-Up (Tabulation):
[Base Cases: dp[0], dp[1]] -> Iteratively compute dp[2] -> dp[3] -> ... -> [dp[N]: Final Answer]

5. Classic DP Formulations Deconstructed#

5.1 0/1 Knapsack Recurrence#

Given $n$ items with weights $wt[i]$ and values $val[i]$, and knapsack capacity $W$:

• Time Complexity: $\Theta(n W)$
• Why is it Pseudo-Polynomial? $W$ is an integer value, not the number of inputs. The input size of $W$ in bits is $\log_2 W$. Hence runtime is exponential in terms of input bit length ($O(n \cdot 2^b)$)!
• 1D Space Optimization: By looping capacity $w$ in reverse order (from $W$ down to $wt[i]$), we ensure each item is used at most once while reducing memory from $O(nW)$ to $O(W)$!

5.2 Longest Common Subsequence (LCS)#

For strings $X[0 \dots m-1]$ and $Y[0 \dots n-1]$:

• Computes the longest sequence of characters that appear in both strings in the same relative order (not necessarily contiguous).
• Backtracking from $DP[m][n]$ reconstructs the exact subsequence string in $O(m + n)$ time.

5.3 Matrix Chain Multiplication (MCM)#

Given matrices $A_1, A_2, \dots, A_n$ where $A_i$ has dimension $p_{i-1} \times p_i$:

• Matrix multiplication is associative: $(A_1 A_2) A_3 = A_1 (A_2 A_3)$.
• But the number of scalar multiplications depends drastically on the order:
  • Multiplying $A_{10 \times 100} \times B_{100 \times 5} \times C_{5 \times 50}$:
    • Order $(AB)C$: $(10 \times 100 \times 5) + (10 \times 5 \times 50) = 5{,}000 + 2{,}500 = 7{,}500$ operations.
    • Order $A(BC)$: $(100 \times 5 \times 50) + (10 \times 100 \times 50) = 25{,}000 + 50{,}000 = 75{,}000$ operations! (10× slower!)
• Recurrence:

• Time Complexity: $\Theta(n^3)$, Space Complexity: $\Theta(n^2)$.

6. Real-World Applications#

1. Bioinformatics & Genomics: Needleman-Wunsch (global alignment) and Smith-Waterman (local alignment) algorithms align DNA and amino-acid sequences using 2D DP matrices.
2. Version Control (git diff): Myers diff algorithm finds the shortest edit script (LCS) between two file revisions.
3. Speech Recognition & Telecom: The Viterbi Algorithm decodes hidden states in Hidden Markov Models (HMMs) for natural speech and CDMA mobile phone error-correcting codes.
4. Natural Language Processing: Spell checkers, autocomplete suggestions, and search engines compute Levenshtein Minimum Edit Distance via DP.

7. Implementation in C, C++, and Python with Syntax Logic#

#include <stdio.h>
#include <string.h>

/**
 * C Syntax Logic Note:
 * 1. 1D Array Optimization: Notice dp[w] depends only on previous row dp[w - wt[i]].
 *    Traversing w BACKWARDS from W down to wt[i] prevents overwriting values from
 *    the current item, shrinking space from O(nW) to O(W)!
 * 2. memset(): Rapidly zeroes the buffer in contiguous memory.
 */

int knapsack01(int W, int wt[], int val[], int n) {
    int dp[W + 1];
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n; i++) {
        // Iterate backwards to ensure 0/1 (single item usage) constraint!
        for (int w = W; w >= wt[i]; w--) {
            int take = val[i] + dp[w - wt[i]];
            if (take > dp[w]) {
                dp[w] = take;
            }
        }
    }
    return dp[W];
}