Design& Analysis of Algorithms (CY-502) Unit 2 Notes

Unit 2: Design and Analysis of Algorithms - Short Notes

I. Fundamentals of Algorithm Analysis

Time Complexity

Definition: Measures the amount of time an algorithm takes to run as a function of input size n. It's crucial for comparing algorithm efficiency.
Asymptotic Notations:
- Big-O (O): Upper bound. f(n) = O(g(n)) if ∃ constants c > 0, n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.
- Big-Omega (Ω): Lower bound. f(n) = Ω(g(n)) if ∃ constants c > 0, n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.
- Big-Theta (Θ): Tight bound. f(n) = Θ(g(n)) if f(n) = O(g(n)) and f(n) = Ω(g(n)).
- little-o (o): Strict upper bound. f(n) = o(g(n)) if lim_{n→∞} f(n)/g(n) = 0.
- little-omega (ω): Strict lower bound. f(n) = ω(g(n)) if lim_{n→∞} f(n)/g(n) = ∞.
Average Case Analysis Examples:
- Binary Search: Average comparisons ≈ log₂(n) → O(log n).
  
  [!TIP] Prove by summing probabilities of successful/unsuccessful searches over all positions.
- Quick Sort: Average case recurrence T(n) = 2·(T(k) + T(n-k-1)) + Θ(n) with uniform pivot → O(n log n).
Proving Asymptotic Bounds:
- Example: f(n) = 5n² + 6n + 4 is O(n²).
  - Find c, n₀: For n ≥ 5, 5n² + 6n + 4 ≤ 5n² + 6n² + 4n² = 15n². So c = 15, n₀ = 5 works.

Space Complexity

Definition: Amount of memory an algorithm uses as a function of input size n.
Examples:
- Iterative algorithms: Usually O(1) auxiliary space.
- Recursive algorithms: O(height of recursion tree) stack space (e.g., Merge Sort O(log n), Quick Sort worst O(n)).
- DP tables: O(n²) or O(nW) for knapsack.

II. Divide and Conquer Paradigm

General Method: Break problem into subproblems, solve recursively, combine solutions. Recurrence: T(n) = a·T(n/b) + f(n).
Merge Sort:
- Algorithm:
  1. Divide array into halves.
  2. Recursively sort each half.
  3. Merge two sorted halves in O(n) time.
- Time Complexity: T(n) = 2T(n/2) + Θ(n) → O(n log n).
Quick Sort:
- Partition Algorithm:
  1. Choose pivot (e.g., last element).
  2. Rearrange: elements < pivot left, > pivot right.
  3. Return pivot index.
- Complexity:
  - Average: O(n log n) (balanced partitions).
  - Worst: O(n²) (already sorted with bad pivot).
Strassen's Matrix Multiplication:
- Recurrence: T(n) = 7T(n/2) + Θ(n²) (7 recursive calls, n² additions).
- Solution: By Master Theorem, a=7, b=2, f(n)=Θ(n²), log_b a = log₂ 7 ≈ 2.807. Since n² = O(n^{log₂ 7 - ε}) for ε≈0.807, T(n) = Θ(n^{log₂ 7}) ≈ O(n^{2.807}).
- Numerical Example: Multiply two 2×2 matrices with 7 multiplications instead of 8.
  
  DiagramCANVAS: Strassen's algorithm steps for 2x2 matrices A and B, showing M1 to M7 calculations and final C matrix composition

III. Greedy Algorithms

Characteristics:
- Greedy Choice Property: Local optimal choice leads to global optimum.
- Optimal Substructure: Problem's optimal solution contains optimal solutions to subproblems.
Correctness Proof: Often via exchange argument or greedy stays ahead.
Fractional Knapsack:
- Greedy: Sort items by profit/weight ratio p_i/w_i descending. Take as much as possible of each.
- Example: n=4, m=15, p=(10,10,12,18), w=(2,4,6,9).
  - Ratios: 5, 2.5, 2, 2. Take all of item1 (w=2), all of item2 (w=4), all of item3 (w=6), remaining 15-12=3 of item4 (w=9).
  - Profit = 10+10+12+(3/9)·18 = 36.
Job Sequencing with Deadlines:
- Greedy: Sort by profit descending. Schedule each job in latest available slot ≤ deadline.
- Example: n=6, p=(200,180,190,300,120,100), d=(5,3,2,4,2,4).
  - Sort by profit: Job4(300,d4), Job1(200,d5), Job3(190,d2), Job2(180,d3), Job5(120,d2), Job6(100,d4).
  - Schedule: Slot4: Job4, Slot5: Job1, Slot3: Job2, Slot2: Job3 (Job5 conflicts, skip).
  - Total profit = 300+200+180+190 = 870.
Optimal Merge Pattern / Huffman Coding:
- Tree Construction:
  1. Create min-heap of frequencies.
  2. Extract two smallest, merge (sum frequencies), reinsert.
  3. Repeat until one node.
- Code Generation: Traverse tree: left=0, right=1.
- Example: Frequencies {a:5, b:9, c:12, d:13, e:16, f:45}.
  - Merges: 5+9=14, 12+13=25, 14+16=30, 25+30=55, 45+55=100.
  - Codes: f:0, c:100, d:101, a:1100, b:1101, e:111.
Minimum Spanning Tree (Greedy):
- Prim's Algorithm:
  - Start from arbitrary vertex. Grow tree by adding cheapest edge connecting tree to new vertex.
  - With priority queue: O(E log V).
- Kruskal's Algorithm:
  - Sort all edges by weight. Add edges in order, skipping cycles (use Union-Find).
  - With union-find: O(E log E) (dominated by sorting).

IV. Dynamic Programming

vs Divide and Conquer:

| Divide & Conquer | Dynamic Programming | |---|---| | Subproblems independent | Subproblems overlap | | Top-down (recursive) | Bottom-up (tabulation) or top-down (memoization) | | No reuse of solutions | Store solutions in table |
Features:
- Optimal Substructure: Global optimum from optimum of subproblems.
- Overlapping Subproblems: Same subproblems solved repeatedly.
Multistage Graph Problem:
- Forward Approach: f[i] = min_{j>i} (cost(i,j) + f[j]), f[n] = 0.
- Backward Approach: f[i] = min_{j>i} (cost(i,j) + f[j]), compute from stage n-1 down to 1.
- Example: Stages 1→2→3→4, costs given. Compute f[1] = min path cost from start to end.
0/1 Knapsack Problem:
- DP Table Formulation: V[i,w] = max( V[i-1,w], V[i-1,w-w_i] + p_i ) for w_i ≤ w, else V[i-1,w].
- i: items considered, w: current capacity.
- Example: N=3, m=6, p=(1,2,5), w=(2,3,4).
  - Table V[3][6]:
    
    | | w=0 | w=1 | w=2 | w=3 | w=4 | w=5 | w=6 | |---|---|---|---|---|---|---|---| | i=0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | i=1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | | i=2 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | | i=3 | 0 | 0 | 1 | 2 | 5 | 5 | 6 |
  - Max profit = V[3][6] = 6 (items 1 & 3).
Floyd-Warshall Algorithm:
- All Pairs Shortest Path.
- Recurrence: d_{ij}^{(k)} = min( d_{ij}^{(k-1)}, d_{ik}^{(k-1)} + d_{kj}^{(k-1)} ).
  - d_{ij}^{(k)}: shortest path from i to j using vertices {1,...,k} as intermediates.
- Algorithm: Initialize d_{ij} = weight(i,j) (∞ if no edge, 0 if i=j). For k=1..n, for all i,j, update d_{ij} = min(d_{ij}, d_{ik}+d_{kj}).
- Example: Given graph with adjacency matrix, compute d after each k.

V. Backtracking

General Method: Systematically explore state space tree, prune branches that cannot yield solution (constraint violations).
N-Queens Problem:
- Algorithm: Place queens row-wise. For each row r, try each column c. Check if (r,c) is safe (no conflict with previously placed queens in same column or diagonal). Recurse to next row. Backtrack if no safe column.
- State Space Tree for 4-Queens:
  
  DiagramCANVAS: State space tree for 4-Queens showing partial placements and backtracking points. Root: row1, branches to col1,2,3,4; each branch explores row2 placements, etc.

Graph Coloring (m-coloring):

Algorithm:


mColoring(graph, m, colors):

  if all vertices colored: return true

  for c in 1..m:

    if safe(v, c):  // no neighbor has color c

      color[v] = c

      if mColoring(next vertex): return true

      color[v] = 0  // backtrack

  return false

Example: Color given graph with m=3.

Hamiltonian Cycle:
- Backtracking: Start at vertex 0. Build path recursively. Add vertex v if not in path and edge exists from last vertex. If path length n and edge from last to start, cycle found.

VI. Branch and Bound

General Method: Systematically enumerate candidate solutions via state space tree, but prune branches using bounding functions (lower/upper bounds on best solution in that branch). Use best-first (e.g., priority queue) or depth-first with bounds.
Traveling Salesperson Problem (TSP):
- Reduction Method:
  1. Cost Matrix Reduction: For each row, subtract row min; for each col, subtract col min. Sum of reductions = initial lower bound.
  2. Bounding: For partial path i→j, set row i and col j to ∞ (avoid reuse). Reduce matrix again, add reduction cost to current bound.
  3. State Space Tree: Nodes represent partial tours. Use priority queue (min-heap) by lower bound.
- Example: Given cost matrix, compute reductions and expand nodes.
vs Backtracking:

| Backtracking | Branch and Bound | |---|---| | Exhaustive search with pruning | Uses bounds to prune non-promising branches | | Depth-first typically | Can be best-first, breadth-first, etc. | | No cost estimation | Bounding function estimates best possible solution in subtree |

VII. Complexity Theory

Decision Problems: Problems with yes/no answer.
Complexity Classes:
- P: Problems solvable in polynomial time by deterministic TM.
- NP: Problems verifiable in polynomial time (or solvable by nondeterministic TM in poly-time).
NP-Hard: At least as hard as hardest NP problems. ∀ L ∈ NP, L ≤p H (H is NP-hard). May not be in NP.
NP-Complete: In NP and NP-hard. ∀ L ∈ NP, L ≤p C and C ∈ NP.
Reductions for NP-Completeness:
1. Show problem ∈ NP (certificate verification poly-time).
2. Reduce known NP-complete problem (e.g., 3-SAT, Clique) to it in poly-time.
Examples:
- TSP (decision version): "Is there tour ≤ K?" → NP-complete.
- 0/1 Knapsack (decision): "Is there subset with profit ≥ P?" → NP-complete.
Relationship:
```
P ⊆ NP ⊆ NP-Hard

      ↑

  NP-Complete = NP ∩ NP-Hard
```
[!TIP] P vs NP: Does P = NP? Unsolved. NP-complete problems are "hardest" in NP.

VIII. Specialized Algorithms and Topics

Horner's Algorithm:
- Polynomial Evaluation: P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ.
- Nested Multiplication: P(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ) ... ).
- Algorithm:
```
Horner(P, x):

  result = aₙ

  for i = n-1 downto 0:

    result = result * x + aᵢ

  return result
```
- Time Complexity: O(n).
- Example: P(x)=2+3x+5x³ at x=2: ((5*2)+0)*2+3)*2+2 = 46.
B-Trees:
- Structure: Order m (each node 2..m children, 1..m-1 keys). All leaves at same depth.
- Insertion: Insert in leaf, split if overflow (propagate).
- Advantages for Disk-Based Systems: Minimize disk accesses (high fan-out reduces height). Balanced, sorted.
Lower Bound Theory:
- Concept: Minimum comparisons needed for any algorithm solving problem.
- Sorting: Ω(n log n) comparisons (decision tree height ≥ log₂(n!) ≈ n log n).
- Searching in Sorted Array: Ω(log n) (binary search optimal).
- Algebraic Problems: E.g., matrix multiplication lower bound Ω(n²) (trivial), but Strassen shows O(n^{2.807}) possible.
Data Stream Algorithms:
- Processing streaming data with limited memory (one pass).
- Examples:
  - Frequent Items: Misra-Gries algorithm (heavy hitters).
  - Distinct Count: Flajolet-Martin algorithm (probabilistic).
Logic Optimization:
- Boolean Function Minimization: Reduce logic gates.
- K-maps: Visual grouping for up to 4 variables.
- Quine-McCluskey: Tabular method for many variables (systematic but exponential).
Parallel Algorithms:
- Concurrent execution on multiple processors.
- Speedup: S(p) = T(1)/T(p). Ideal linear speedup S(p)=p.
- Examples:
  - Parallel Sorting: Bitonic sort O(log² n) time with n processors.
  - Matrix Multiplication: Each element computed independently → O(n²) with n² processors.

[!IMPORTANT] Exam Tips from Past Papers:

Always state recurrence for D&C (Merge Sort, Strassen's).

For greedy proofs, use exchange argument: show any optimal solution can be transformed to greedy solution without worsening cost.

DP table: Clearly define V[i,w] or d[i][j] and fill step-by-step.

Backtracking: Draw state space tree for N-Queens (4 or 8).

Branch and Bound TSP: Show cost matrix reduction step-by-step.

NP-Completeness: Reduction must be polynomial time. Know classic reductions (e.g., Clique → Vertex Cover).

Numerical Examples: Past papers frequently ask for specific inputs—practice with given values.

Account

Design& Analysis of Algorithms (CY-502) - Unit 2 Short Notes

Unit 2: Design and Analysis of Algorithms - Short Notes

I. Fundamentals of Algorithm Analysis

Time Complexity

Space Complexity

II. Divide and Conquer Paradigm

III. Greedy Algorithms

IV. Dynamic Programming

V. Backtracking

VI. Branch and Bound

VII. Complexity Theory

VIII. Specialized Algorithms and Topics