CS8451

Design and Analysis of Algorithms

7 Files
•
CSE Department
Download Progress 0/7 files
Unit 1
Notes Not downloaded 274 KB
Unit 2
Notes Not downloaded 309 KB
Unit 3
Notes Not downloaded 254 KB
Unit 4
Notes Not downloaded 186 KB
Unit 5
Notes Not downloaded 297 KB
Important Questions
Study Not downloaded 352 KB
Previous Year Question Paper
Exam Not downloaded 793 KB
Academic Study Guide

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 all n ≥ nâ‚€.
    • Big-Omega (Ω): Lower bound representing best-case performance. Formally: f(n) ≥ c · g(n) for all n ≥ 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 as n → ∞.
  • Master Theorem for Divide & Conquer: For recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1:
    • Case 1: If f(n) = O(n^(log_b(a) - ε)), then T(n) = Θ(n^(log_b a)).
    • Case 2: If f(n) = Θ(n^(log_b a) · log^k(n)), then T(n) = Θ(n^(log_b a) · log^(k+1)(n)).
    • Case 3: If f(n) = Ω(n^(log_b(a) + ε)) and regular condition a·f(n/b) ≤ c·f(n) holds, then T(n) = Θ(f(n)).

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 with O(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²), yielding O(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])) if wt[i] ≤ w. Solved via a 2D table in O(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]; else L[i,j] = max(L[i-1, j], L[i, j-1]) in O(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 problem Y ∈ NP is 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 SortDivide & ConquerO(n log n)O(n log n)O(n log n)O(n)
Quick SortDivide & ConquerO(n log n)O(n log n)O(n²)O(log n)
Binary SearchDecrease & ConquerO(1)O(log n)O(log n)O(1)
0/1 KnapsackDynamic ProgrammingO(n · W)O(n · W)O(n · W)O(n · W)
Fractional KnapsackGreedy MethodO(n log n)O(n log n)O(n log n)O(1)
Dijkstra’s AlgorithmGreedy (Heap)O((V+E) log V)O((V+E) log V)O((V+E) log V)O(V)
Floyd-WarshallDynamic ProgrammingO(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.