Design & Analysis of Algorithms (DAA) Comprehensive Curriculum Guide
Algorithm design and complexity analysis form the core mathematical backbone of computer science. This study guide covers asymptotic notations, divide-and-conquer principles, greedy strategies, dynamic programming recurrence relations, branch-and-bound optimization, and NP-completeness theory aligned with AICTE, Anna University, and VTU curricula.
Unit-by-Unit Theoretical Revision
Unit 1: Foundations of Algorithm Analysis & Recurrences
An algorithm is a finite sequence of unambiguous instructions for solving a computational problem, requiring finiteness, definiteness, input, output, and effectiveness.
- Asymptotic Notations:
- Big-O (O): Upper bound representing worst-case growth rate. Formally:
f(n) ≤ c · g(n)for alln ≥ n₀. - Big-Omega (Ω): Lower bound representing best-case performance. Formally:
f(n) ≥ c · g(n)for alln ≥ n₀. - Big-Theta (Θ): Asymptotically tight bound holding both upper and lower bounds simultaneously:
c₠· g(n) ≤ f(n) ≤ c₂ · g(n). - Little-o (o) and Little-omega (ω): Strict loose asymptotic bounds where the limit of
f(n)/g(n)equals 0 and ∞ respectively asn → ∞.
- Big-O (O): Upper bound representing worst-case growth rate. Formally:
- Master Theorem for Divide & Conquer: For recurrences of the form
T(n) = aT(n/b) + f(n)wherea ≥ 1, b > 1:- Case 1: If
f(n) = O(n^(log_b(a) - ε)), thenT(n) = Θ(n^(log_b a)). - Case 2: If
f(n) = Θ(n^(log_b a) · log^k(n)), thenT(n) = Θ(n^(log_b a) · log^(k+1)(n)). - Case 3: If
f(n) = Ω(n^(log_b(a) + ε))and regular conditiona·f(n/b) ≤ c·f(n)holds, thenT(n) = Θ(f(n)).
- Case 1: If
Unit 2: Divide-and-Conquer Paradigm
Divide-and-Conquer partitions a problem into smaller independent subproblems of the same type, solves them recursively, and combines their solutions.
- Merge Sort: Divides array into two halves at midpoint, recursively sorts, and merges using two pointers. Recurrence:
T(n) = 2T(n/2) + Θ(n)yielding strictlyΘ(n log n)time across all cases withO(n)auxiliary space. Stable sorting technique. - Quick Sort: Selects a pivot element and partitions array such that elements smaller than pivot precede it and greater elements follow it. Recurrence: Best/Average case
T(n) = 2T(n/2) + Θ(n) → Θ(n log n). Worst case (sorted array with extreme pivot)T(n) = T(n-1) + Θ(n) → Θ(n²). In-place sorting technique. - Strassen’s Matrix Multiplication: Multiplies two 2×2 block matrices using 7 multiplications instead of 8 standard multiplications. Recurrence:
T(n) = 7T(n/2) + Θ(n²), yieldingO(n^(log₂ 7)) ≈ O(n^2.807).
Unit 3: Greedy Technique & Dynamic Programming
Greedy algorithms construct solutions piece by piece choosing the immediate best option. Dynamic Programming (DP) solves problems with overlapping subproblems and optimal substructure by caching results.
- Fractional Knapsack (Greedy): Calculates value-to-weight ratio
v_i / w_i, sorts items descending, and greedily selects items, accepting fractional parts. Time complexity:O(n log n). - 0/1 Knapsack (Dynamic Programming): Items cannot be divided. Recurrence:
K(i, w) = max(K(i-1, w), val[i] + K(i-1, w - wt[i]))ifwt[i] ≤ w. Solved via a 2D table inO(n · W)pseudo-polynomial time. - Longest Common Subsequence (LCS): Finds maximum length matching subsequence between strings X and Y. Recurrence: If
X[i] == Y[j],L[i,j] = 1 + L[i-1, j-1]; elseL[i,j] = max(L[i-1, j], L[i, j-1])inO(m · n)time. - Huffman Coding: Greedy prefix code generation using min-heaps to build optimal binary trees for lossless data compression in
O(n log n)time.
Unit 4: Backtracking & Branch-and-Bound
Explores the state space tree using systematic pruning of non-promising candidate branches.
- Backtracking (DFS with Pruning):
- N-Queens Problem: Places N non-attacking queens on an N×N chessboard. Backtracks immediately if two queens share a row, column, or diagonal.
- Subset Sum Problem: Generates subsets whose sum equals target S using bounding conditions to prune subtrees exceeding S.
- Hamiltonian Circuit: Finds closed tours visiting each graph vertex exactly once.
- Branch-and-Bound (BFS/Priority Search): Uses cost functions and estimated lower bounds to prune subtrees for optimization problems. Applied to the Traveling Salesperson Problem (TSP) using reduced cost matrices.
Unit 5: Complexity Classes, P, NP & NP-Completeness
- Class P: Problems solvable in polynomial time
O(n^k)by a deterministic Turing machine (e.g., Shortest Paths, Minimum Spanning Trees). - Class NP: Decision problems whose solution candidates can be verified in polynomial time by a deterministic algorithm, or solved in polynomial time by a non-deterministic machine.
- NP-Complete (NPC): A problem X is NP-complete if: (1)
X ∈ NP, and (2) Every problemY ∈ NPis polynomial-time reducible to X (Y ≤_p X). Examples: SAT, 3-SAT, Vertex Cover, Clique, Traveling Salesperson Decision. - NP-Hard: Problems at least as hard as any problem in NP, but not necessarily in NP (e.g., Halting Problem).
Algorithmic Paradigms & Complexity Comparison
| Algorithm | Design Paradigm | Best Time | Average Time | Worst Time | Auxiliary Space |
|---|---|---|---|---|---|
| Merge Sort | Divide & Conquer | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Divide & Conquer | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Binary Search | Decrease & Conquer | O(1) | O(log n) | O(log n) | O(1) |
| 0/1 Knapsack | Dynamic Programming | O(n · W) | O(n · W) | O(n · W) | O(n · W) |
| Fractional Knapsack | Greedy Method | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Dijkstra’s Algorithm | Greedy (Heap) | O((V+E) log V) | O((V+E) log V) | O((V+E) log V) | O(V) |
| Floyd-Warshall | Dynamic Programming | O(V³) | O(V³) | O(V³) | O(V²) |
High-Frequency University Exam Questions
Q1: State the Master Theorem and evaluate T(n) = 2T(n/2) + n.
Comparing T(n) = 2T(n/2) + n with aT(n/b) + f(n) gives a = 2, b = 2, f(n) = n. We evaluate n^(log_b a) = n^(log₂ 2) = n¹ = n. Since f(n) = Θ(n^(log_b a)), this matches Master Theorem Case 2 with k = 0. Therefore, the time complexity is T(n) = Θ(n log n).
Q2: Compare Dynamic Programming with the Greedy Method. When does Greedy fail?
Greedy algorithms make irrevocable local choices without reconsidering previous steps. Dynamic Programming systematically considers all subproblem options, caching intermediate solutions. Greedy fails when local optimality does not yield global optimality, such as in the 0/1 Knapsack problem where taking the highest value-to-weight ratio item may prevent optimal packing of remaining capacity.
Q3: Explain the difference between NP-Complete and NP-Hard problems with examples.
A problem is NP-Hard if every problem in NP is polynomial-time reducible to it; it does not need to belong to NP itself. A problem is NP-Complete if it is both NP-Hard and explicitly belongs to NP (meaning solutions can be verified in polynomial time). The Halting Problem is NP-Hard but not NP-Complete (it is undecidable). 3-SAT, Vertex Cover, and Hamiltonian Cycle are NP-Complete.