Data Structures & Algorithms Algorithmic Paradigms Syllabus

Give an example where greedy fails but DP succeeds, in the context of coin change.

For coin denominations $\{1,3,4\}$ making 6, greedy gives $4+1+1=3$ coins, but DP finds the optimum $3+3=2$ coins. Greedy is not optimal for arbitrary denominations.

Define dynamic programming.

A technique that solves problems by breaking them into overlapping subproblems, solving each subproblem once, and storing its result (memoization or tabulation) to avoid recomputation, exploiting optimal substructure.

What two properties must a problem have for dynamic programming to apply?

Optimal substructure (an optimal solution is built from optimal subsolutions) and overlapping subproblems (the same subproblems recur many times).

Contrast top-down memoization with bottom-up tabulation.

Top-down (memoization): recursion computes subproblems on demand and caches results. Bottom-up (tabulation): iteratively fills a table from base cases upward. Tabulation avoids recursion overhead; memoization only computes needed states.

How do you estimate the time complexity of a DP algorithm?

Time $\approx$ (number of distinct states) $\times$ (work per state / transition cost). For example, a 2D table with $O(1)$ transitions is $O(mn)$.

State the recurrence and complexity for the DP solution to the Fibonacci sequence.

$F(n)=F(n-1)+F(n-2)$ with $F(0)=0,\ F(1)=1$. With memoization or tabulation it is $O(n)$ time and can be $O(1)$ space, versus $O(\phi^{n})$ for naive recursion.

Give the DP recurrence for the maximum subarray sum (Kadane's algorithm).

$dp[i]=\max(a_i,\ dp[i-1]+a_i)$, and the answer is $\max_i dp[i]$. It runs in $O(n)$ time and $O(1)$ space.

State the DP recurrence for climbing stairs (1 or 2 steps at a time).

$dp[i]=dp[i-1]+dp[i-2]$ with $dp[0]=1,\ dp[1]=1$. The number of ways equals the Fibonacci-like count, $O(n)$ time.

What is the DP recurrence for the House Robber problem (no two adjacent)?

$dp[i]=\max\big(dp[i-1],\ dp[i-2]+a_i\big)$, choosing to skip or rob house $i$. It is $O(n)$ time, $O(1)$ space.

State the DP recurrence for the Longest Increasing Subsequence (LIS) in $O(n^{2})$.

$dp[i]=1+\max\{dp[j]:j<i,\ a_j<a_i\}$ (or $1$ if none), with answer $\max_i dp[i]$. An $O(n\log n)$ patience-sorting variant also exists.

Give the DP recurrence for edit distance (Levenshtein) between strings $A$ and $B$.

$dp[i][j]=dp[i-1][j-1]$ if $A_i=B_j$; otherwise $dp[i][j]=1+\min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1])$, for delete, insert, and replace. Complexity $O(mn)$.

State the DP recurrence for the Longest Common Subsequence (LCS) of $A$ and $B$.

$dp[i][j]=dp[i-1][j-1]+1$ if $A_i=B_j$; otherwise $dp[i][j]=\max(dp[i-1][j],\ dp[i][j-1])$. Time and space $O(mn)$.

Give the DP recurrence for counting unique paths in an $m\times n$ grid (moves right/down).

$dp[i][j]=dp[i-1][j]+dp[i][j-1]$ with base cases $dp[0][j]=dp[i][0]=1$. Closed form: $\binom{m+n-2}{m-1}$.

State the recurrence for minimum path sum in a grid with cost $c_{i,j}$.

$dp[i][j]=c_{i,j}+\min(dp[i-1][j],\ dp[i][j-1])$, with the top-left as the base case. Complexity $O(mn)$.

What is the DP recurrence for the 0/1 knapsack problem?

$dp[i][w]=\max\big(dp[i-1][w],\ dp[i-1][w-w_i]+v_i\big)$ when $w_i\leq w$, else $dp[i][w]=dp[i-1][w]$. Complexity $O(nW)$ (pseudo-polynomial).

Why is 0/1 knapsack called pseudo-polynomial rather than polynomial?

Its $O(nW)$ running time depends on the numeric value $W$ (capacity), which requires $\log W$ bits to encode, so it is exponential in the input size in bits, not truly polynomial.

How does the unbounded knapsack recurrence differ from 0/1 knapsack?

Items may be reused, so the transition references the same item row: $dp[w]=\max(dp[w],\ dp[w-w_i]+v_i)$, iterating capacity in increasing order so each item can be taken multiple times.

In a 1D-array 0/1 knapsack implementation, why must the capacity loop run in decreasing order?

Iterating $w$ from high to low ensures each item is used at most once; ascending order would allow the same item to be counted multiple times (turning it into unbounded knapsack).

State the DP for the subset-sum / partition-equal-subset problem.

Boolean DP: $dp[s]$ = whether sum $s$ is achievable. Transition $dp[s] = dp[s]\ \lor\ dp[s-a_i]$ (capacity descending). For equal partition, target $= \frac{1}{2}\sum a_i$ and total must be even.

Give the DP recurrence for the coin-change minimum-coins problem.

$dp[a]=\min_{c\in\text{coins},\ c\leq a}\big(dp[a-c]+1\big)$ with $dp[0]=0$ and $dp[a]=\infty$ if unreachable. Complexity $O(a\cdot|\text{coins}|)$.

What is the general recurrence pattern for DP on trees using a post-order traversal?

Compute each node's DP value from its children's values after they are solved: $dp[u]=f\big(\{dp[v]:v\in\text{children}(u)\}\big)$. A common form keeps two states per node (included / excluded).

State the tree DP for maximum independent set (weighted, no two adjacent nodes) on a rooted tree.

For each node $u$: $incl[u]=w_u+\sum_{v\in child(u)} excl[v]$ and $excl[u]=\sum_{v\in child(u)}\max(incl[v],\ excl[v])$. Answer $=\max(incl[root],\ excl[root])$.

How is DP applied to shortest paths in a DAG?

Process vertices in topological order; for each vertex relax outgoing edges: $dist[v]=\min(dist[v],\ dist[u]+w(u,v))$. This gives $O(V+E)$ single-source shortest paths on a DAG, even with negative weights.

What DP algorithm computes all-pairs shortest paths, and what is its recurrence?

Floyd–Warshall: $dp^{(k)}[i][j]=\min\big(dp^{(k-1)}[i][j],\ dp^{(k-1)}[i][k]+dp^{(k-1)}[k][j]\big)$, iterating $k$ over all intermediate vertices. Complexity $O(V^{3})$.

Define backtracking as an algorithmic paradigm.

A systematic, depth-first search that incrementally builds candidate solutions and abandons (backtracks from) a candidate as soon as it determines the candidate cannot be extended to a valid complete solution.

Write the general backtracking template in pseudocode.

backtrack(state): if state is a complete solution -> record it; else for each choice in candidates(state): if valid(choice): apply(choice); backtrack(state); undo(choice). The undo step restores state after exploring a branch.

Give three classic problems solved by backtracking.

The N-Queens problem, generating all permutations/subsets, and constraint puzzles such as Sudoku and graph coloring.

What is pruning in backtracking, and why is it important?

Pruning discards branches of the search tree that cannot lead to a valid or optimal solution (via constraint checks or bounds), drastically reducing explored states and turning exponential search into a practical one.

Distinguish constraint-based pruning from bounding (branch and bound).

Constraint-based pruning cuts branches that violate feasibility (e.g., two queens attacking). Bounding (branch and bound) computes an optimistic bound on a partial solution's objective and prunes branches that cannot beat the best solution found so far.

What is the state space of a search problem, and how does branch and bound explore it?

The state space is the tree/graph of all partial and complete configurations reachable by sequential choices. Branch and bound explores it by branching into subproblems and using bounds to prune non-promising nodes, often with a best-first (priority-queue) order.

Define the Travelling Salesman Problem (TSP) and its optimal-tour objective.

Given $n$ cities and pairwise distances $d(i,j)$, find a minimum-cost Hamiltonian cycle visiting each city exactly once and returning to the start, minimizing $\sum_{k} d(\pi_k,\pi_{k+1})$. TSP is NP-hard.

What is the Held–Karp dynamic programming complexity for exact TSP, and how does it compare to brute force?

Held–Karp runs in $O(n^{2}2^{n})$ time and $O(n\,2^{n})$ space, a major improvement over brute-force enumeration of all $(n-1)!$ tours, though still exponential.