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

UNIT 5: DESIGN & ANALYSIS OF ALGORITHMS

I. FOUNDATIONS OF ALGORITHM ANALYSIS

Algorithm Definition & Characteristics

• Definition: A finite sequence of well-defined instructions for solving a specific problem.

• Characteristics: Input, Output, Definiteness, Finiteness, Effectiveness.

Time Complexity Analysis

• Best Case: Minimum time required (e.g., binary search finds target in first comparison).

• Average Case: Expected time over all inputs. Requires probability distribution of inputs.

• Worst Case: Maximum time required (e.g., binary search exhausts all comparisons).

• [!TIP] Exam Focus: Average case analysis often involves summing costs over all possible input positions and dividing by n.

Average Case Analysis of Binary Search (Dec 2024)

• Problem: Find expected number of comparisons in successful search.

• Model: Assume all n elements equally likely to be searched.

• Derivation:

  • For an element at depth i (root depth 0), comparisons = i+1.

  • Number of nodes at depth i in a complete binary tree: ≤ 2^i.

  • Total comparisons C(n) ≈ Σ_{i=0}^{h} (i+1) * min(2^i, n - (2^i - 1)), where h = ⌊log₂ n⌋.

  • Simplified: C(n) ≈ (n+1)⌊log₂(n+1)⌋ - 2^{⌊log₂(n+1)⌋+1} + 2.

  • Result: C(n) = Θ(log n). Hence, average case is O(log n).

  \boxed{\text{Average Case Time Complexity of Binary Search} = O(\log n)}

Average Case Analysis of Quicksort (Nov 2022)

• Model: Pivot chosen uniformly at random; all n! permutations equally likely.

• Recurrence for expected comparisons C(n):

$$C(n) = n-1 + \frac{1}{n} \sum_{k=0}^{n-1} [C(k) + C(n-k-1)]$$

• Solution: C(n) ≈ 2n ln n = O(n log n).

• [!TIP] Key insight: Each pair of elements is compared only if one is chosen as pivot before any element between them. Probability = 2/(j-i+1).

Asymptotic Notations

• Big-O (O): Upper bound. f(n) = O(g(n)) iff ∃ c>0, n₀ s.t. 0 ≤ f(n) ≤ c*g(n) ∀ n ≥ n₀.

• Big-Omega (Ω): Lower bound. f(n) = Ω(g(n)) iff ∃ c>0, n₀ s.t. 0 ≤ c*g(n) ≤ f(n) ∀ n ≥ n₀.

• Big-Theta (Θ): Tight bound. f(n) = Θ(g(n)) iff f(n) = O(g(n)) and f(n) = Ω(g(n)).

• Little-o (o): Strict upper bound. f(n) = o(g(n)) iff lim_{n→∞} f(n)/g(n) = 0.

• Little-omega (ω): Strict lower bound. f(n) = ω(g(n)) iff lim_{n→∞} g(n)/f(n) = 0.

Proving Asymptotic Bounds (Nov 2022 Example)

• Claim: f(n) = 5n² + 6n + 4 is O(n²).

• Proof: For n ≥ 1, 5n² + 6n + 4 ≤ 5n² + 6n² + 4n² = 15n². Choose c=15, n₀=1. Hence proved.

  \boxed{5n^2 + 6n + 4 = O(n^2)}

Space Complexity

• Total Space: Space used by algorithm + input + output.

• Auxiliary Space: Extra/temporary space used by algorithm (excluding input/output).

• [!TIP] Short Note (Dec 2024): Auxiliary space is crucial for recursive algorithms (stack space) and in-place algorithms (constant auxiliary space).

II. DIVIDE AND CONQUER (D&C) PARADIGM

General Method & Recurrence Relations

1. Divide: Break problem into smaller subproblems.

2. Conquer: Solve subproblems recursively.

3. Combine: Merge subproblem solutions.

• Solving Recurrences:

  • Substitution Method: Guess solution, verify by induction.

  • Recursion Tree: Visualize cost per level, sum costs.

  • Master Theorem: For T(n) = aT(n/b) + f(n):

    \boxed{

    T(n) =

    \begin{cases}

    \Theta(n^{\log_b a}) & \text{if } f(n)=O(n^{\log_b a - \epsilon}) \

    \Theta(n^{\log_b a} \log n) & \text{if } f(n)=\Theta(n^{\log_b a}) \

    \Theta(f(n)) & \text{if } f(n)=\Omega(n^{\log_b a + \epsilon}) \text{ and } af(n/b) \leq cf(n)

    \end{cases}

    }

Strassen's Matrix Multiplication (Dec 2024, Nov 2022)

• Algorithmic Steps:

  1. Partition n×n matrices A, B into four n/2 × n/2 submatrices.

  2. Compute 7 products (P₁ to P₇) recursively:

     • P₁ = (A₁₁ + A₂₂) × (B₁₁ + B₂₂)

     • P₂ = (A₂₁ + A₂₂) × B₁₁

     • P₃ = A₁₁ × (B₁₂ - B₂₂)

     • P₄ = A₂₂ × (B₂₁ - B₁₁)

     • P₅ = (A₁₁ + A₁₂) × B₂₂

     • P₆ = (A₂₁ - A₁₁) × (B₁₁ + B₁₂)

     • P₇ = (A₁₂ - A₂₂) × (B₂₁ + B₂₂)

  3. Combine to get result submatrices:

     • C₁₁ = P₁ + P₄ - P₅ + P₇

     • C₁₂ = P₃ + P₅

     • C₂₁ = P₂ + P₄

     • C₂₂ = P₁ - P₂ + P₃ + P₆

• Recurrence: T(n) = 7T(n/2) + Θ(n²) (7 recursive calls, Θ(n²) for additions).

• Solution by Master Theorem: a=7, b=2, log_b a ≈ 2.81. Since f(n)=Θ(n²) = O(n^{2.81-ε}), Case 1 applies.

  \boxed{T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})}

Merge Sort

• Algorithm:

  1. If n > 1:

     • Divide array into two halves.

     • Recursively sort left and right halves.

     • Merge two sorted halves in Θ(n) time.

• Time Complexity: T(n) = 2T(n/2) + Θ(n). Master Theorem Case 2: T(n) = Θ(n log n) (best, average, worst).

  \boxed{T_{\text{merge sort}}(n) = \Theta(n \log n)}

Quicksort (Dec 2024)

• Algorithm (Lomuto Partitioning):

  
  QUICKSORT(A, low, high):
  
      if low < high:
  
          p = PARTITION(A, low, high)  // pivot final index
  
          QUICKSORT(A, low, p-1)
  
          QUICKSORT(A, p+1, high)
  
  PARTITION(A, low, high):
  
      pivot = A[high]
  
      i = low - 1
  
      for j = low to high-1:
  
          if A[j] ≤ pivot:
  
              i = i+1; swap A[i] and A[j]
  
      swap A[i+1] and A[high]
  
      return i+1
  
  

• Example (Dec 2024): A = {6, 15, 3, 14, 25, 36, 18}. First pivot=18. After partition: {6,15,3,14,18,36,25}. Recurse on left {6,15,3,14} and right {36,25}.

• Time Complexity:

  • Worst Case (already sorted): T(n) = T(n-1) + Θ(n) = Θ(n²).

  • Best Case (balanced): T(n) = 2T(n/2) + Θ(n) = Θ(n log n).

  • Average Case (random pivot): Θ(n log n) (proved earlier).

III. GREEDY ALGORITHM PARADIGM

General Method & Greedy Choice Property

• Method: At each step, make a locally optimal choice hoping for global optimum.

• Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.

• Optimal Substructure: Optimal solution contains optimal solutions to subproblems.

• [!TIP] Correctness Proof (Nov 2022): Often by exchange argument or staying ahead.

Fractional/Continuous Knapsack (Dec 2024, Nov 2023, Nov 2022)

• Problem: Maximize profit with weight capacity m. Items can be taken fractionally.

• Greedy Strategy: Sort items by profit/weight ratio (p_i/w_i) descending. Take as much as possible of each item in order until capacity full.

• Example (Dec 2024):

  n=4, m=15, p=(10,10,12,18), w=(2,4,6,9)

  • Ratios: 5, 2.5, 2, 2.

  • Sort by ratio: Item1 (5), Item2 (2.5), Item3 (2), Item4 (2).

  • Take full Item1 (w=2, p=10, rem cap=13).

  • Take full Item2 (w=4, p=10, rem cap=9).

  • Take full Item3 (w=6, p=12, rem cap=3).

  • Take 3/9 = 1/3 of Item4 (p=6).

  • Total Profit = 10+10+12+6 = 38.

  \boxed{\text{Optimal Profit (Fractional Knapsack)} = 38}

Job Sequencing with Deadlines (Dec 2024, Nov 2023)

• Problem: Schedule jobs (each takes 1 unit time) to maximize total profit, each job must finish by its deadline.

• Greedy Strategy:

  1. Sort all jobs by profit descending.

  2. Find maximum deadline max_d.

  3. Create array slot[1..max_d] initialized empty.

  4. For each job in sorted order:

     • Find latest empty slot ≤ job.deadline.

     • If found, schedule job there.

• Example (Dec 2024):

  n=6, p=(200,180,190,300,120,100), d=(5,3,2,4,2,4)

  • Sort by profit: J4(300,d4), J1(200,d5), J3(190,d2), J2(180,d3), J5(120,d2), J6(100,d4).

  • Schedule:

    • J4 → slot 4.

    • J1 → slot 5.

    • J3 → slot 2.

    • J2 → slot 3.

    • J5 → no slot (d2 full).

    • J6 → slot 1? Wait, slot1 empty? Let's check: slots 1,2,3,4,5. After J4(s4), J1(s5), J3(s2), J2(s3): slots 1 empty. J6(d4) → slot1? No, slot1 ≤4, but we schedule backwards. Actually, for J6, find latest empty ≤4: slots 4,3,2 full, slot1 empty → schedule at slot1? But typical algorithm schedules at latest possible. Let's redo properly:

    • Slots: [1,2,3,4,5]

    • J4(300,d4) → slot4 → [_,_,_,300,_]

    • J1(200,d5) → slot5 → [_,_,_,300,200]

    • J3(190,d2) → slot2 → [_,190,_,300,200]

    • J2(180,d3) → slot3 → [_,190,180,300,200]

    • J5(120,d2) → no slot ≤2 (slot2 full).

    • J6(100,d4) → no slot ≤4 (slots 2,3,4 full).

  • Scheduled Jobs: J4, J1, J3, J2. Total Profit = 300+200+190+180 = 870.

  \boxed{\text{Optimal Profit (Job Sequencing)} = 870}

Optimal Merge Pattern / Huffman Coding (Dec 2024, Nov 2023, Nov 2022)

• Problem: Merge k sorted files with lengths l₁, l₂, ..., lₖ into one file. Cost of merging two files of lengths a,b is a+b. Minimize total cost.

• Greedy Strategy: Always merge the two smallest files first. Use a min-heap.

• Huffman Coding: Optimal prefix-free binary codes for characters with frequencies.

  1. Create min-heap of nodes (char, freq).

  2. While heap size > 1:

     • Extract two smallest nodes x, y.

     • Create new node z with freq = x.freq + y.freq, left=x, right=y.

     • Insert z into heap.

  3. The final node is root of Huffman tree. Traverse to assign codes (left=0, right=1).

• Example (Frequencies: a:5, b:9, c:12, d:13, e:16, f:45):

  • Merge 5+9=14 → heap: (12,13,14,16,45)

  • Merge 12+13=25 → heap: (14,16,25,45)

  • Merge 14+16=30 → heap: (25,30,45)

  • Merge 25+30=55 → heap: (45,55)

  • Merge 45+55=100.

  • Codes: f:0, c:100, d:101, a:1100, b:1101, e:111.

IV. DYNAMIC PROGRAMMING (DP) PARADIGM

Characteristics & Comparison with Divide & Conquer (Dec 2024)

Algorithmic Steps:

1. Characterize optimal substructure.

2. Define value of optimal solution recursively.

3. Compute value bottom-up (tabulation) or top-down with memoization.

4. Construct optimal solution from computed information.

0/1 Knapsack Problem (Dec 2024, Nov 2022)

• Problem: Given n items (profit p_i, weight w_i), capacity m. Each item either taken (1) or not (0). Maximize total profit without exceeding m.

• DP Table: dp[i][w] = max profit using first i items with capacity w.

• Recurrence:

$$ dp[i][w] = \begin{cases} 0 & \text{if } i=0 \text{ or } w=0 \\ dp[i-1][w] & \text{if } w_i > w \\ \max(p_i + dp[i-1][w-w_i], dp[i-1][w]) & \text{otherwise} \end{cases} $$

• Example (Nov 2022): n=3, m=6, p=(1,2,5), w=(2,3,4).

  • Table dp[4][7] (rows 0..3, cols 0..6).

  • Fill row-wise. Final dp[3][6] = 5 (take item3 only).

  • Optimal Profit = 5.

Multistage Graph Problem (Dec 2024, Nov 2023)

• Problem: Directed acyclic graph with stages 1..k. Find minimum cost path from start (stage 1) to end (stage k).

• Forward DP Approach:

  • Let f_i(v) = min cost from vertex v in stage i to end.

  • Base: f_k(v) = cost(v, terminal) for v in stage k.

  • Recurrence: f_i(v) = min_{u∈adj(v)} [ cost(v,u) + f_{i+1}(u) ].

  • Compute from stage k-1 down to 1.

• Backward DP: Similar but compute from start.

• Path Reconstruction: At each vertex v in stage i, choose u that minimizes cost(v,u)+f_{i+1}(u).

All-Pairs Shortest Paths: Floyd-Warshall (Nov 2023)

• Algorithm:

  1. Initialize distance matrix D with D[i][j] = weight(i,j) (∞ if no edge, 0 if i=j).

  2. For k = 1 to n:

     • For i = 1 to n:

       • For j = 1 to n:

         • D[i][j] = min(D[i][j], D[i][k] + D[k][j])

• Time Complexity: Θ(n³).

• Path Reconstruction: Maintain predecessor matrix P. Update P[i][j] = P[k][j] if D[i][k]+D[k][j] improves.

Optimal Binary Search Tree (OBST)

• Problem: Given keys k₁<..<kₙ with search probabilities p₁..pₙ (and dummy keys d₀..dₙ), construct BST minimizing expected search cost.

• DP: e[i][j] = expected cost of subtree containing k_i+1..k_j.

  • e[i][j] = min_{i≤r≤j} { e[i][r-1] + e[r+1][j] + w(i,j) }, where w(i,j)=Σ_{s=i+1}^j p_s + Σ_{s=i}^j q_s.

• Complexity: O(n³) naive, O(n²) with Knuth's optimization if probabilities satisfy quadrangle inequality.

V. BACKTRACKING PARADIGM

General Method & State Space Tree

• Method: Systematically explore solution space via depth-first search with pruning (backtrack when partial solution cannot be extended to a full solution).

• State Space Tree: Nodes represent partial solutions. Root = initial state. Leaves = complete solutions or dead ends.

• Efficiency: Depends on ability to prune early.

N-Queens Problem (Dec 2024)

• Problem: Place n queens on n×n chessboard so no two attack each other (no same row, column, diagonal).

• Backtracking Algorithm:

  
  NQUEENS(row):
  
      if row > n: print solution; return
  
      for col = 1 to n:
  
          if PLACE(row, col) is safe:
  
              set queen at (row, col)
  
              NQUEENS(row+1)
  
              remove queen from (row, col)  // backtrack
  
  PLACE(row, col):
  
      for i = 1 to row-1:
  
          if queen at (i, col) or 
  
             queen at (i, row-i+col) or  // main diagonal
  
             queen at (i, row+col-i):    // anti-diagonal
  
              return false
  
      return true
  
  

• State Space Tree for 4-Queens (Nov 2022):

  • Root → 4 branches (col1-col4 for row1).

  • Each branch tries cols for row2, prune if conflict.

  • Leaves at depth 4 are solutions (e.g., [2,4,1,3] meaning queen at (1,2), (2,4), (3,1), (4,3)).

  DiagramCANVAS: A tree with root, first level 4 nodes (row1 placements). From each, some branches die early. Only two leaves at depth 4 survive: one with path [2,4,1,3] and another [3,1,4,2].

Graph Coloring Problem (m-coloring) (Nov 2023, Nov 2022)

• Problem: Color vertices of graph with m colors so no adjacent vertices share color.

• Backtracking Algorithm:

  
  COLOR(v):
  
      if v > n: return true  // all colored
  
      for c = 1 to m:
  
          if SAFE(v, c):  // check all neighbors of v
  
              color[v] = c
  
              if COLOR(v+1): return true
  
              color[v] = 0  // backtrack
  
      return false
  
  

• Solving for Given Graph: Assign colors sequentially, backtrack on conflict.

Hamiltonian Cycle Problem (Nov 2022)

• Problem: Find cycle visiting each vertex exactly once and returning to start.

• Backtracking Algorithm:

  
  HAMILTONIAN(path, pos):
  
      if pos == n:  // all vertices in path
  
          if edge exists from last to start: print path; return true
  
          else: return false
  
      for each vertex v not in path:
  
          if edge exists from path[pos-1] to v:
  
              path[pos] = v
  
              if HAMILTONIAN(path, pos+1): return true
  
              path[pos] = -1  // backtrack
  
      return false
  
  

• Example: For graph with vertices 1,2,3,4 and edges (1-2,2-3,3-4,4-1), path [1,2,3,4] with edge 4-1 gives cycle.

VI. BRANCH AND BOUND (B&B) PARADIGM

General Method (Dec 2024)

• Systematic Enumeration of candidate solutions using state space tree.

• Key Concepts:

  • Live Node: Node generated but not fully explored.

  • Dead Node: Node that cannot produce better solution (pruned).

  • E-node (Expanding Node): Live node being explored.

  • Cost Function (ĉ): Estimate of cost of any solution reachable from node. Must satisfy ĉ(node) ≥ cost(optimal solution in subtree).

• Search Strategies:

  • FIFO (Breadth-First): Queue. Explore level by level.

  • LIFO (Depth-First): Stack. Explore one branch to leaf before backtracking.

  • Least Cost Search (Best-First): Priority queue ordered by ĉ. Most promising node expanded first.

Traveling Salesperson Problem (TSP) using Reduction (Dec 2024, Nov 2023)

• Problem: Find minimum cost Hamiltonian cycle in weighted graph.

• Reduction Method (Cost Matrix Reduction):

  1. Row Reduction: For each row, subtract row minimum from all elements in that row. Sum of subtracted values = cost_so_far.

  2. Column Reduction: For each column, subtract column minimum.

  3. Total Lower Bound: cost_so_far (from step 1) + sum of column minima (step 2).

  4. Branching: For each edge (i,j) not yet fixed:

     • Include edge: Set row i and column j to ∞ (to prevent other edges from same row/col), and also set (j,i)=∞ to prevent subtour. Compute new lower bound.

     • Exclude edge: Set (i,j)=∞. Compute new lower bound.

  5. Choose node with smallest lower bound to expand next (Least Cost).

• Bounding Function: Reduced cost matrix's total reduction + current path cost.

• Example: Start with 4×4 cost matrix. Reduce rows/cols, get initial bound. Branch on edge with smallest reduced cost (often 0 if present). Continue until a complete tour is found with cost C. Prune any live node with bound ≥ C.

0/1 Knapsack using B&B

• Node: Represents decision on first i items (some taken, some not).

• State: (i, current_weight, current_profit).

• Bounding: Compute upper bound on profit achievable from node:

  • Fill remaining capacity greedily (fractionally) with items by p/w ratio.

  • bound = current_profit + (remaining_capacity * next_item_ratio) (if items sorted by ratio).

• Branching: At node (i, w, p), create two children:

  • Left (include item i+1): (i+1, w+w_{i+1}, p+p_{i+1})

  • Right (exclude item i+1): (i+1, w, p)

• Pruning: Discard node if bound ≤ best_profit_so_far or weight > capacity.

VII. NP-HARDNESS & NP-COMPLETENESS

Complexity Classes

• P: Decision problems solvable in polynomial time by deterministic Turing machine.

• NP: Decision problems verifiable in polynomial time (or solvable by nondeterministic TM in poly time).

  • P ⊆ NP (all P problems are in NP).

• NP-Hard: Problems at least as hard as hardest problems in NP. Every NP problem reduces to them in poly time. Not necessarily in NP.

• NP-Complete: Problems that are both NP-Hard and in NP.

  • If any NP-Complete has poly-time solution, then P=NP.

Polynomial Time Reductions

• Definition: Transform instances of problem A to instances of problem B in polynomial time, such that answer is "yes" for A iff "yes" for B.

• Purpose: Show B is at least as hard as A. If A is NP-Hard and A ≤ₚ B, then B is NP-Hard.

• Common Reductions:

  • SAT → 3-SAT: Convert clauses to 3-literal form using new variables.

  • Clique → Vertex Cover: Graph G has clique of size k iff G has vertex cover of size |V|-k.

  • Vertex Cover → Independent Set: S is vertex cover iff V\S is independent set.

  • Subset Sum → Partition: Special case.

Comparison: NP-Hard vs NP-Complete (Dec 2024, Nov 2023, Nov 2022)

Classic NP-Complete Problems

• Boolean Satisfiability (SAT): Given Boolean formula, is there satisfying assignment? (Cook-Levin theorem: first NP-Complete).

• Clique: Does graph contain complete subgraph of size k?

• Vertex Cover: Does graph have vertex cover of size k?

• Subset Sum: Given set of integers, is there subset summing to K?

• Traveling Salesperson Problem (Decision): Given graph and K, is there tour with cost ≤ K?

• 0/1 Knapsack (Decision): Given items, capacity m, profit P, is there subset with total weight ≤ m and total profit ≥ P?

VIII. ADVANCED & SPECIALIZED TOPICS (SHORT NOTES)

Horner's Algorithm for Polynomial Evaluation (Dec 2024)

• Problem: Evaluate polynomial P(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ at point x.

• Naive: Θ(n²) operations (compute each x^k separately).

• Horner's Rule: Rewrite as P(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ) ... ).

• Algorithm:

  
  result = a_n
  
  for i = n-1 downto 0:
  
      result = result * x + a_i
  
  return result
  
  

• Complexity: Θ(n) multiplications/additions.

• Example: P(x)=2+3x+4x² → ((4)*x + 3)*x + 2.

Prim's Algorithm for MST (Dec 2024)

• Problem: Find minimum spanning tree (connected, acyclic, all vertices, min total edge weight) of undirected graph.

• Algorithm (using min-heap):

  1. Start with arbitrary vertex s in MST.

  2. Maintain min-heap of edges connecting MST to outside vertices, keyed by edge weight.

  3. While heap not empty:

     • Extract min edge (u,v) where u∈MST, v∉MST.

     • Add v and edge to MST.

     • For each neighbor w of v not in MST, insert/update heap edge (v,w).

• Time Complexity:

  • With binary heap: O((V+E) log V) = O(E log V) (since E ≥ V-1).

  • With array (no heap): O(V²).

• Working Example: For given graph, show step-by-step addition of vertices and edges with min weight.

B-Trees (Nov 2023)

• Definition: Self-balancing search tree where each node can have multiple keys and multiple children.

• Properties:

  • All leaves at same depth.

  • Node with k children has k-1 keys.

  • Keys in node sorted; keys in subtree i are between keys i-1 and i.

  • Order t (minimum degree): Each node (except root) has at least t-1 keys, at most 2t-1 keys. Root at least 1 key.

  • Height h = O(log_t n).

• Creation (Insertion): Search leaf, insert key in sorted order. If overflow (2t keys), split middle key to parent.

• Advantages over BST:

  • Better for disk/storage (fewer disk accesses due to high branching factor).

  • Always balanced (no need for rotations like AVL/Red-Black).

  • Efficient for range queries.

Parallel Algorithms (Dec 2024, Nov 2023, Nov 2022)

• Definition: Algorithms designed to run on multiple processors/cores simultaneously.

• Models: PRAM (Parallel Random Access Machine) - shared memory, processors execute synchronously.

• Key Metrics:

  • Work: Total operations across all processors = T₁ (sequential time).

  • Time: T_p with p processors.

  • Speedup: S_p = T₁ / T_p.

  • Efficiency: E_p = S_p / p = T₁ / (p T_p).

  • Parallelism: T₁ / T_∞ (max speedup with unlimited processors).

• Examples:

  • Parallel Merge Sort: Divide array, sort halves in parallel, merge in parallel.

  • Matrix Multiplication (Cannon's, Fox's): Assign blocks to processors.

• Challenges: Load balancing, synchronization, communication overhead.

Data Stream Algorithms (Nov 2023, Nov 2022)

• Context: Data arrives as a stream (high volume, one-pass, limited memory).

• Goal: Compute summaries/statistics without storing all data.

• Key Problems & Algorithms:

  • Counting Distinct Elements (Heavy Hitters): Flajolet-Martin algorithm, HyperLogLog.

  • Frequent Items (Misra-Gries, Count-Min Sketch): Find items with frequency > εN.

  • Quantiles (Greenwald-Khanna): Approximate median, percentiles.

  • Windowed Queries (Sliding Windows): Count in last W elements (using exponential histograms).

• Example: HyperLogLog estimates number of distinct IP addresses in a stream using O(log log n) memory with small error.

Logic Optimization (Nov 2023, Nov 2022)

• Goal: Simplify Boolean functions (circuits) to minimize cost (gate count, delay, power).

• Techniques:

  • Algebraic Simplification: Using Boolean identities (x+x'=1, x·1=x, etc.).

  • Karnaugh Map (K-map): Graphical method for up to 6 variables. Group adjacent 1s to find prime implicants.

  • Quine-McCluskey Method: Tabular method for many variables. Find prime implicants, then essential primes, then cover with minimal set.

  • Espresso Algorithm: Heuristic for large functions (two-level logic).

• Example: Simplify f(a,b,c) = Σ(0,1,2,4,5,6) using K-map → f = b' + a'c'.

Traveling Salesperson Problem (TSP) Short Note (Dec 2024)

• Problem: Given weighted graph (complete or not), find Hamiltonian cycle of minimum total cost.

• Exact Methods:

  • Branch and Bound (Reduction): As described above. Works for small n (≤20).

  • Dynamic Programming (Held-Karp): O(n² 2ⁿ) time, O(n 2ⁿ) space. State: (S, i) = min cost to visit set S ending at i.

• Approximate Methods:

  • Nearest Neighbor: Start at city, repeatedly go to nearest unvisited. Fast (O(n²)), but can be bad (up to log n factor).

  • Minimum Spanning Tree (MST) Based: Double MST (preorder walk) gives 2-approximation for metric TSP (triangle inequality). Christofides algorithm gives 1.5-approximation.

  • Genetic Algorithms, Simulated Annealing: Metaheuristics for large instances.

• Complexity: NP-Hard (decision version is NP-Complete). No poly-time algorithm unless P=NP.

END OF UNIT 5 NOTES