Unit 4: Dynamic Programming and graph algorithms
Design and Analysis of Algorithm notes · PTU syllabus (UGCC2519)
On this page
Unit summary
Dynamic programming (DP) solves problems with overlapping subproblems by solving each subproblem once and storing its answer. This unit applies DP to Fibonacci numbers, binomial coefficients, all-pairs shortest paths (Floyd-Warshall) and the 0/1 knapsack problem, and covers two graph algorithms: connected components and topological sorting.
After this unit you can
- Explain dynamic programming, memoisation and tabulation
- Compute Fibonacci numbers and binomial coefficients with DP
- Solve all-pairs shortest paths with Floyd-Warshall
- Solve 0/1 knapsack, find connected components and topologically sort a DAG
PTU syllabus topics
- General concept
- Fibonacci series and binomial coefficient computation
- all-pairs shortest paths (Floyd-Warshall)
- 0/1 Knapsack problem
- finding connected components
- topological sorting
Decision
Best local choice, never revisited
Considers all subproblems
Optimal
Not always
Always, when the problem fits
Memory
Low
Stores a table of results
Example
Fractional knapsack
0/1 knapsack, Floyd-Warshall
Topic 1
The dynamic programming approach
DP applies when a problem has optimal substructure and overlapping subproblems.
Subproblems
Independent
Overlapping
Repeats work?
May solve the same subproblem many times
Solves each once and stores it
Example
Merge sort
Fibonacci, knapsack, Floyd-Warshall
- Memoisation (top-down): recursion plus a table to remember results.
- Tabulation (bottom-up): fill a table from the smallest subproblems up.
Topic 2
Fibonacci and binomial coefficients
- Plain recursive Fibonacci is O(2ⁿ) because it recomputes values; with DP, F[i] = F[i − 1] + F[i − 2] in a loop is O(n).
- Binomial coefficient C(n, k) = C(n − 1, k − 1) + C(n − 1, k), with C(n, 0) = C(n, n) = 1. Building Pascal's triangle row by row takes O(nk).
Example
C(5, 2) from Pascal's triangle row 5 (1, 5, 10, 10, 5, 1) is 10.
Topic 3
Floyd-Warshall: all-pairs shortest paths
Floyd-Warshall finds the shortest path between every pair of vertices. For each intermediate vertex k, update: D[i][j] = min(D[i][j], D[i][k] + D[k][j]) It uses three nested loops, so it takes O(V³) time, and works with negative edges (but not negative cycles).
Topic 4
0/1 knapsack
Each item is either taken whole or not at all. Let K[i][w] be the best profit using the first i items with capacity w: K[i][w] = max(K[i − 1][w], pᵢ + K[i − 1][w − wᵢ]) if wᵢ ≤ w, otherwise K[i − 1][w]. Time O(nW).
Example
W = 5; items (w, p): (2, 3), (3, 4), (4, 5). Best is items 1 and 2: weight 5, profit 7.
Topic 5
Connected components and topological sorting
- Connected components: run DFS or BFS from each unvisited vertex; each run discovers one component. O(V + E).
- Topological sort of a directed acyclic graph (DAG) orders vertices so every edge u → v has u before v. Methods: DFS finishing order reversed, or Kahn's algorithm (repeatedly remove vertices with in-degree 0).
Example
Course prerequisites: Maths → DS → Algorithms and Maths → DBMS. One topological order: Maths, DS, DBMS, Algorithms.
Key terms
- Dynamic programming
- Solving overlapping subproblems once and storing results
- Memoisation
- Top-down caching of recursive results
- Floyd-Warshall
- All-pairs shortest path algorithm, O(V³)
- 0/1 knapsack
- Knapsack where items cannot be split
- Topological sort
- Linear order of a DAG respecting edge directions
Quick revision
- DP = optimal substructure + overlapping subproblems.
- Fibonacci DP O(n); C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
- Floyd-Warshall: D[i][j] = min(D[i][j], D[i][k] + D[k][j]).
- 0/1 knapsack: K[i][w] = max(skip, take).
- Topological sort only for DAGs.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What are the two properties needed for dynamic programming?
- Q2.Differentiate between memoisation and tabulation.
- Q3.Write the recurrence for the binomial coefficient.
- Q4.What is the time complexity of Floyd-Warshall?
- Q5.What is a topological sort?
Long-answer questions
- Q1.Compare divide and conquer, greedy and dynamic programming approaches.
- Q2.Solve the all-pairs shortest path problem for a graph using Floyd-Warshall.
- Q3.Solve a 0/1 knapsack problem using dynamic programming with the full table.
- Q4.Explain topological sorting with an example using Kahn's algorithm.
Stuck on this unit?
Message SBS on WhatsApp for help with Design and Analysis of Algorithm, or to ask about studying BCA at Synetic.