UNIT 1: Design & Analysis of Algorithms – Comprehensive Short Notes

I. Fundamentals of Algorithm Analysis

Algorithm Definition & Characteristics

• Definition: A finite sequence of well-defined, unambiguous instructions to solve a specific problem, producing an output for any valid input in finite time.

• Characteristics:

  1. Input: Zero or more quantities supplied externally.

  2. Output: At least one quantity produced.

  3. Definiteness: Each instruction is clear and precise.

  4. Finiteness: Terminates after a finite number of steps.

  5. Effectiveness: Each instruction is basic and feasible.

• Algorithm Design Techniques (Paradigms): Divide & Conquer, Greedy, Dynamic Programming, Backtracking, Branch & Bound.

Complexity Analysis: Time & Space

• Time Complexity: Measures the amount of time an algorithm takes as a function of input size n. Typically, we count the number of primitive operations (comparisons, arithmetic, assignments).

• Space Complexity: Measures the amount of memory (auxiliary space) used as a function of input size n. Includes space for input, output, and temporary working storage.

• Cases:

  • Best-case: Minimum time/space over all inputs of size n.

  • Average-case: Expected time/space over all inputs of size n (requires probability distribution).

  • Worst-case: Maximum time/space over all inputs of size n (most commonly analyzed).

• Examples:

  • Binary Search: Worst & average-case time complexity is $O(\log n)$.

  • Quick Sort: Worst-case $$\displaystyle O(n^2) $$, average-case $O(n \log n)$.

Asymptotic Notations & Mathematical Proofs

• Formal Definitions (for functions $f(n), g(n)$):

  • Big-O (Upper Bound): $$\displaystyle f(n) = O(g(n)) $$ if $\exists$ positive constants $$\displaystyle c, n_0 $$ such that $0 \le f(n) \le c \cdot g(n)$ for all $$\displaystyle n \ge n_0 $$.

  • Omega (Ω) (Lower Bound): $$\displaystyle f(n) = \Omega(g(n)) $$ if $\exists$ positive constants $$\displaystyle c, n_0 $$ such that $0 \le c \cdot g(n) \le f(n)$ for all $$\displaystyle n \ge n_0 $$.

  • Theta (Θ) (Tight Bound): $$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$.

  • Little-o (Upper Bound, not tight): $$\displaystyle f(n) = o(g(n)) $$ if $$\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $$.

  • Little-omega (Lower Bound, not tight): $$\displaystyle f(n) = \omega(g(n)) $$ if $$\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty $$.

• Common Properties:

  • Transitivity: If $$\displaystyle f = O(g) $$ and $$\displaystyle g = O(h) $$, then $$\displaystyle f = O(h) $$.

  • Symmetry for Θ: $$\displaystyle f = \Theta(g) \iff g = \Theta(f) $$.

• Proof Example: Show $$\displaystyle f(n) = 5n^2 + 6n + 4 $$ is $$\displaystyle O(n^2) $$.

  For $n \ge 1$, $$\displaystyle 5n^2 + 6n + 4 \le 5n^2 + 6n^2 + 4n^2 = 15n^2 $$. Choose $$\displaystyle c = 15 $$, $$\displaystyle n_0 = 1 $$. Thus, $$\displaystyle f(n) \le 15n^2 $$ for $n \ge 1$, so $$\displaystyle f(n) = O(n^2) $$.

Solving Recurrence Relations

• Recurrence Formulation: Expresses the running time of a recursive algorithm in terms of its input size (e.g., $$\displaystyle T(n) = aT(n/b) + f(n) $$ for divide & conquer).

• Methods:

  1. Substitution Method: Guess a bound, then prove by induction.

  2. Recursion Tree Method: Visualize the recurrence as a tree, sum costs per level.

  3. Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $$\displaystyle a \ge 1, b > 1 $$:

     • If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$ for $$\displaystyle \epsilon > 0 $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a}) $$.

     • If $$\displaystyle f(n) = \Theta(n^{\log_b a}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a} \log n) $$.

     • If $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$ and $af(n/b) \le cf(n)$ for $$\displaystyle c < 1 $$, then $$\displaystyle T(n) = \Theta(f(n)) $$.

• Example: Strassen's: $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$. Here, $$\displaystyle a=7, b=2, \log_b a = \log_2 7 \approx 2.807 $$. Since $$\displaystyle f(n) = \Theta(n^2) = O(n^{\log_2 7 - \epsilon}) $$ for $\epsilon \approx 0.807$, by Case 1, $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}) $$.

Lower Bound Theory

• Concept: A lower bound $\Omega(f(n))$ for a problem means no algorithm can solve it faster than $f(n)$ (asymptotically).

• Comparison-based Problems:

  • Sorting: Any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the worst case (decision tree argument: $n!$ permutations $\Rightarrow$ height $$\displaystyle \ge \log_2(n!) = \Omega(n \log n) $$).

  • Searching in a sorted array: $\Omega(\log n)$ comparisons (binary search achieves this bound).

• Algebraic Problems:

  • Matrix Multiplication: Naive method is $$\displaystyle O(n^3) $$. Strassen's is $$\displaystyle O(n^{2.807}) $$. The conjectured lower bound is $$\displaystyle \Omega(n^2) $$ (since reading input is $$\displaystyle \Omega(n^2) $$), but a tight bound is unknown.

Correctness Proof of Greedy Algorithms

• Key Properties:

  • Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step.

  • Optimal Substructure: An optimal solution to the problem contains within it optimal solutions to subproblems.

• Proof Method (Exchange Argument):

  1. Let $S$ be the solution produced by the greedy algorithm.

  2. Let $O$ be an optimal solution.

  3. Show that the first greedy choice is in some optimal solution (by exchange argument: if not, replace the first choice in $O$ with the greedy choice to get another optimal solution).

  4. Use induction: after the first greedy choice, the remaining subproblem is solved optimally by the greedy algorithm (by optimal substructure).

• Example: Fractional Knapsack (greedy by profit/weight ratio works), 0/1 Knapsack (greedy fails).

II. Divide and Conquer Paradigm

General Method & Recurrence Relations

• Steps:

  1. Divide: Break the problem into a number of subproblems (usually smaller instances of the same problem).

  2. Conquer: Solve the subproblems recursively. If small enough, solve directly.

  3. Combine: Combine the solutions to the subproblems to form the solution to the original problem.

• Recurrence: $$\displaystyle T(n) = aT(n/b) + D(n) + C(n) $$, where $a$ = number of subproblems, $n/b$ = size of each subproblem, $D(n)$ = cost of divide, $C(n)$ = cost of combine.

• Analysis: Use recursion tree or Master Theorem.

Merge Sort

• Algorithm:

  1. If $$\displaystyle n = 1 $$, return the array (already sorted).

  2. Divide: Split array $A[low..high]$ into two halves $A[low..mid]$ and $A[mid+1..high]$.

  3. Conquer: Recursively sort both halves.

  4. Combine: Merge the two sorted halves into a single sorted array.

• Merging Process: Standard linear-time merge (like in merge step of merge sort). Compare front elements of two subarrays, copy smaller to output, advance pointer. $O(n)$ time.

• Time Complexity: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$. By Master Theorem (Case 2), $$\displaystyle T(n) = \Theta(n \log n) $$ in all cases (best, average, worst).

• Space Complexity: $O(n)$ auxiliary space for the temporary merge array (not in-place).

Quick Sort

• Algorithm:

  1. Partition: Rearrange array $A[p..r]$ so that all elements $\le$ pivot (often $A[r]$) are left of pivot, all $$\displaystyle > $$ pivot are right. Pivot is in its final sorted position. Return pivot index $q$.

  2. Recursively sort $A[p..q-1]$ and $A[q+1..r]$.

• Partition Procedure (Lomuto/Hoare):

  • Lomuto: Pivot = $A[r]$, index $$\displaystyle i = p-1 $$, for $$\displaystyle j=p $$ to $r-1$, if $A[j] \le$ pivot, $i++$, swap $A[i], A[j]$. Finally swap $A[i+1], A[r]$, return $i+1$.

  • Hoare: More efficient, fewer swaps on average.

• Time Complexity:

  • Worst-case: $$\displaystyle O(n^2) $$. Occurs when partition is maximally unbalanced (e.g., array already sorted, pivot is smallest/largest). Recurrence: $$\displaystyle T(n) = T(n-1) + \Theta(n) $$.

  • Average-case: $O(n \log n)$. Assumes random pivot or random input. Recurrence on average: $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) $$, solved to $O(n \log n)$.

• Example: Sort $$\displaystyle A = \{6, 15, 3, 14, 25, 36, 18\} $$ (using last element as pivot).

  • First partition (pivot=18): $\{6,15,3,14,18,36,25\}$. Pivot at index 4.

  • Recurse left: $\{6,15,3,14\}$ (pivot=14) → $\{6,3,14,15\}$.

  • Recurse right: $\{36,25\}$ (pivot=25) → $\{25,36\}$.

  • Final sorted: $\{3,6,14,15,18,25,36\}$.

Binary Search

• Algorithm (Iterative):

  
  BinarySearch(A, low, high, key):
  
      while low <= high:
  
          mid = floor((low + high) / 2)
  
          if A[mid] == key: return mid
  
          else if A[mid] < key: low = mid + 1
  
          else: high = mid - 1
  
      return NOT_FOUND
  
  

• Recursive: Similar, with base case low > high.

• Time Complexity:

  • Best-case: $O(1)$ (key is middle element).

  • Worst-case: $O(\log n)$ (key not present or at leaf).

  • Average-case Derivation:

    Let $C(n)$ be average comparisons. For $n$ elements, after one comparison, search continues in subarray of size $\approx n/2$ (if key not found at mid). Assuming key equally likely in any position:

$$C(n) = 1 + \frac{1}{n} \sum_{k=0}^{n-1} C\left(\left\lfloor \frac{n-1}{2} \right\rfloor \text{ or } \left\lceil \frac{n-1}{2} \right\rceil\right) \approx 1 + C(n/2)$$

    Solving: $$\displaystyle C(n) = O(\log n) $$.

Strassen's Algorithm for Matrix Multiplication

• Problem: Multiply two $n \times n$ matrices $A, B$ to get $$\displaystyle C = A \times B $$.

• Naive Method: $$\displaystyle O(n^3) $$ (three nested loops).

• Strassen's Approach (for $n$ a power of 2):

  1. Divide each matrix into four $n/2 \times n/2$ submatrices.

  2. Compute 7 (not 8) recursive multiplications of submatrices ($$\displaystyle P_1 $$ to $$\displaystyle P_7 $$).

  3. Combine results using 18 additions/subtractions of $n/2 \times n/2$ matrices to get the four quadrants of $C$.

• Recurrence: $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$ (since 18 additions take $$\displaystyle \Theta(n^2) $$).

• Solution: By Master Theorem (Case 1), $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}) $$.

• Example: Given a $2 \times 4$ matrix? [Note: Strassen requires square matrices of size power of 2. For non-square, pad with zeros.] For a $2 \times 2$ block:

$$ \begin{bmatrix} A & B \\ C & D \end{bmatrix} \times \begin{bmatrix} E & F \\ G & H \end{bmatrix} $$

Compute:

$$\displaystyle P_1 = A(F-H) $$, $$\displaystyle P_2 = (A+B)H $$, $$\displaystyle P_3 = (C+D)E $$, $$\displaystyle P_4 = D(G-E) $$, $$\displaystyle P_5 = (A+D)(E+H) $$, $$\displaystyle P_6 = (B-D)(G+H) $$, $$\displaystyle P_7 = (A-C)(E+F) $$.

Then:

$$\displaystyle C_{11} = P_5 + P_4 - P_2 + P_6 $$,

$$\displaystyle C_{12} = P_1 + P_2 $$,

$$\displaystyle C_{21} = P_3 + P_4 $$,

$$\displaystyle C_{22} = P_5 + P_1 - P_3 - P_7 $$.

III. Greedy Algorithms

General Characteristics

• Greedy Choice Property: Makes the choice that looks best at the moment (local optimum), hoping it leads to a global optimum.

• Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.

• When Greedy Works: For problems where local optimal choices lead to a global optimum (e.g., Fractional Knapsack, Huffman, MST).

• When Greedy Fails: For problems where a locally optimal choice may preclude a globally optimal solution (e.g., 0/1 Knapsack, general shortest path with negative weights?).

Fractional Knapsack Problem

• Problem: $n$ items, each with profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$. Knapsack capacity $m$. Can take fractions of items. Maximize total profit.

• Greedy Strategy: Compute profit/weight ratio $$\displaystyle r_i = p_i / w_i $$ for each item. Sort items in decreasing order of $$\displaystyle r_i $$. Take as much as possible of the item with highest $$\displaystyle r_i $$ until either it's exhausted or knapsack is full. Repeat with next item.

• Algorithm:

  1. Calculate $$\displaystyle r_i = p_i / w_i $$ for all $i$.

  2. Sort items by $$\displaystyle r_i $$ descending.

  3. Initialize total_weight = 0, total_profit = 0.

  4. For each item in sorted order:

     • If total_weight + w_i <= m: take whole item, update totals.

     • Else: take fraction $$\displaystyle (m - total\_weight) / w_i $$, update total_profit, break.

• Time Complexity: $O(n \log n)$ dominated by sorting.

• Example ($$\displaystyle n=4, m=15, p=(10,10,12,18), w=(2,4,6,9) $$):

  • Ratios: $$\displaystyle r_1=5, r_2=2.5, r_3=2, r_4=2 $$. Sorted order: Item1, Item2, Item3, Item4.

  • Take full Item1 (w=2, p=10), total w=2, p=10.

  • Take full Item2 (w=4, p=10), total w=6, p=20.

  • Take full Item3 (w=6, p=12), total w=12, p=32.

  • Remaining capacity = 3. Take $$\displaystyle 3/9 = 1/3 $$ of Item4: profit $$\displaystyle 18*(1/3)=6 $$.

  • Optimal profit = 32 + 6 = 38.

0/1 Knapsack Problem (Greedy Failure)

• Problem: Same as fractional, but items cannot be split (0 or 1 of each).

• Greedy Fails: Taking items by highest $$\displaystyle p_i/w_i $$ may not yield optimal solution.

• Example: Capacity $$\displaystyle m=50 $$, items: (p=60, w=10, r=6), (p=100, w=20, r=5), (p=120, w=30, r=4).

  • Greedy takes item1 (w=10, p=60), item2 (w=20, p=100), total w=30, p=160. Remaining 20 can't take item3.

  • Optimal: Take item2 (w=20, p=100) and item3 (w=30, p=120), total w=50, p=220.

• Optimal Solution: Requires Dynamic Programming (see Unit IV).

Job Sequencing with Deadlines

• Problem: $n$ jobs, each with profit $$\displaystyle p_i $$, deadline $$\displaystyle d_i $$ (1 unit time per job). Schedule jobs to maximize total profit such that each job finishes by its deadline. At most one job per time slot.

• Greedy Strategy:

  1. Sort all jobs in decreasing order of profit.

  2. Find the maximum deadline $$\displaystyle max\_deadline $$.

  3. Create an array slot[1..max_deadline], initialize all to "empty".

  4. For each job in sorted order:

     • Find the latest available slot $s$ (from $$\displaystyle min(d_i, max\_deadline) $$ down to 1) that is empty.

     • If found, schedule job in that slot (slot[s] = job_id).

• Time Complexity: $$\displaystyle O(n^2) $$ with simple array. Can be improved to $O(n \log n)$ using Disjoint Set Union (DSU) to find next available slot quickly.

• Example ($$\displaystyle n=6, p=(200,180,190,300,120,100), d=(5,3,2,4,2,4) $$):

  • Sort by profit: Job4(p=300,d=4), Job1(p=200,d=5), Job3(p=190,d=2), Job2(p=180,d=3), Job5(p=120,d=2), Job6(p=100,d=4).

  • Schedule:

    • Job4: latest free slot ≤4 is slot4 → schedule at t=4.

    • Job1: latest free slot ≤5 is slot5 → schedule at t=5.

    • Job3: latest free slot ≤2 is slot2 → schedule at t=2.

    • Job2: latest free slot ≤3 is slot3 → schedule at t=3.

    • Job5: no free slot ≤2 (slots 1,2 taken? slot1 free but d=2, slot1≤2, so schedule at t=1? Wait, check: after Job3 at t=2, slot1 is free. Job5 d=2, can schedule at t=1? Yes, t=1 ≤ 2. So schedule Job5 at t=1.

    • Job6: no free slot ≤4 (slots 1,2,3,4 taken).

  • Optimal schedule: Jobs 4,1,3,2,5 at times 4,5,2,3,1 respectively. Total profit = 300+200+190+180+120 = 990.

Huffman Coding

• Problem: Given characters with frequencies, construct a prefix-free binary code (no codeword is prefix of another) to minimize expected code length (weighted path length).

• Greedy Strategy: Build a binary tree where each leaf is a character. Repeatedly merge the two nodes with smallest frequencies into a new internal node with frequency = sum.

• Algorithm:

  1. Create a min-priority queue (min-heap) of nodes, keyed by frequency.

  2. For each character, create a leaf node with its frequency and insert into heap.

  3. While heap size > 1:

     • Extract two nodes $x, y$ with smallest frequencies.

     • Create new node $z$ with frequency $$\displaystyle f_z = f_x + f_y $$, left child = $x$, right child = $y$.

     • Insert $z$ into heap.

  4. The remaining node is the root of the Huffman tree.

• Code Assignment: Traverse tree, assign '0' to left edge, '1' to right edge. Codeword for a leaf is the path from root.

• Time Complexity: $O(n \log n)$ due to heap operations (each of $n-1$ merge steps involves 2 extracts and 1 insert).

• Example: Characters: a:5, b:9, c:12, d:13, e:16, f:45.

  • Merge a(5)+b(9)=14 → node14.

  • Merge c(12)+d(13)=25 → node25.

  • Merge node14(14)+e(16)=30 → node30.

  • Merge node25(25)+node30(30)=55 → node55.

  • Merge f(45)+node55(55)=100 → root.

  • Codes: f:0, c:100, d:101, a:1100, b:1101, e:111. Weighted length = $$\displaystyle 5*4 + 9*4 + 12*3 + 13*3 + 16*3 + 45*1 = 20+36+36+39+48+45 = 224 $$.

Optimal Merge Pattern

• Problem: Given $n$ sorted files (or lists) with lengths $$\displaystyle l_1, l_2, ..., l_n $$, merge them into one sorted file. Merging two files of lengths $a$ and $b$ takes $a+b$ operations (or time). Find merging order that minimizes total merge cost (sum of all merge operations).

• Greedy Strategy: Always merge the two smallest files available. This is identical to Huffman coding where file lengths are frequencies.

• Algorithm: Use a min-heap. While more than one file exists, extract two smallest, merge them (cost = sum), insert sum back into heap. Total cost accumulates.

• Time Complexity: $O(n \log n)$.

• Connection: Optimal merge pattern is a special case of constructing an optimal binary search tree or Huffman tree. The total cost equals the weighted external path length of the merge tree.

• Example: Files of sizes: 10, 20, 30, 40.

  • Merge 10+20=30 (cost=30), files: 30,30,40.

  • Merge 30+30=60 (cost=60), files: 40,60.

  • Merge 40+60=100 (cost=100).

  • Total cost = 30+60+100 = 190.

Minimum Spanning Tree (MST) – Prim's & Kruskal's

• Problem: Given a connected, undirected, weighted graph $$\displaystyle G=(V,E) $$, find a spanning tree (connects all vertices, no cycles) with minimum total edge weight.

• Properties: MST has $|V|-1$ edges. Cut property: For any cut, the lightest edge crossing the cut is in some MST.

Prim's Algorithm

• Idea: Grow a single tree from an arbitrary root. At each step, add the minimum weight edge connecting the current tree to a vertex not yet in the tree.

• Algorithm:

  1. Initialize key[v] = ∞ for all $v \in V$, key[r] = 0 for arbitrary root $r$, parent[v] = NIL.

  2. Priority queue $Q$ containing all vertices keyed by key.

  3. While $Q$ not empty:

     • Extract vertex $u$ with minimum key[u].

     • For each neighbor $v$ of $u$ still in $Q$:

       • If weight($u,v$) < key[v], update key[v] = weight(u,v), parent[v] = u.

  4. MST edges are $(parent[v], v)$ for all $v \ne r$.

• Time Complexity:

  • With binary heap: $$\displaystyle O((V+E) \log V) = O(E \log V) $$ (since $E \ge V-1$).

  • With Fibonacci heap: $O(E + V \log V)$.

• Example: Given graph, start at vertex A, repeatedly add cheapest edge to new vertex.

Kruskal's Algorithm

• Idea: Consider edges in increasing order of weight. Add an edge if it does not create a cycle with already selected edges.

• Algorithm:

  1. Sort all edges $E$ by non-decreasing weight.

  2. Initialize a Union-Find (Disjoint Set) data structure with each vertex in its own set.

  3. For each edge $(u,v)$ in sorted order:

     • If Find(u) != Find(v) (adding edge doesn't create cycle), add edge to MST, and Union(u,v).

• Time Complexity:

  • Sorting edges: $$\displaystyle O(E \log E) = O(E \log V) $$ (since $$\displaystyle E \le V^2 $$).

  • Union-Find operations (with union by rank & path compression): nearly $O(\alpha(V))$ per op, so total $O(E \alpha(V))$.

  • Overall: $$\displaystyle O(E \log E) = O(E \log V) $$.

• Example: Given graph, sort edges: (A,B,1), (B,C,2), (A,C,3), (C,D,4), (B,D,5)... Add edges in order if they connect different components.

IV. Dynamic Programming (DP)

Features & Comparison with Divide and Conquer

• Features:

  1. Optimal Substructure: Optimal solution to problem contains optimal solutions to subproblems.

  2. Overlapping Subproblems: Recursive algorithm solves same subproblems repeatedly (unlike D&C where subproblems are usually distinct).

  3. Bottom-up Computation: Solve smaller subproblems first, store solutions in a table (tabulation). Or top-down with memoization (cache results).

• Comparison:

0/1 Knapsack Problem (DP Solution)

• Problem: $n$ items, profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$, capacity $W$. Maximize $$\displaystyle \sum p_i x_i $$ subject to $$\displaystyle \sum w_i x_i \le W $$, $$\displaystyle x_i \in \{0,1\} $$.

• DP Formulation:

  Let $V[i][w]$ = maximum profit obtainable using first $i$ items with capacity $w$.

  Recurrence:

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

• Algorithm (Tabulation):

  1. Initialize table $V[0..n][0..W]$ with zeros.

  2. For $$\displaystyle i = 1 $$ to $n$:

     • For $$\displaystyle w = 1 $$ to $W$:

       • If $$\displaystyle w_i \le w $$: $$\displaystyle V[i][w] = \max(V[i-1][w], V[i-1][w-w_i] + p_i) $$.

       • Else: $$\displaystyle V[i][w] = V[i-1][w] $$.

  3. Answer = $V[n][W]$.

  4. (Optional) Trace back to find selected items.

• Time & Space Complexity: $O(nW)$ (pseudo-polynomial, depends on numeric value of $W$).

• Example ($$\displaystyle n=3, W=6, p=(1,2,5), w=(2,3,4) $$):

  • Table:

*   $$\displaystyle V[3][6] = 6 $$. Items: Item3 (w4,p5) taken? $V[3][6] \ne V[2][6]$ (6≠3), so item3 taken. Remaining capacity $$\displaystyle 6-4=2 $$. $$\displaystyle V[2][2]=1 \ne V[1][2]=1 $$? Actually $$\displaystyle V[2][2]=1 $$, $$\displaystyle V[1][2]=1 $$, so item2 not taken. Check item1: $$\displaystyle V[1][2]=1 \ne V[0][2]=0 $$, so item1 taken. **Items 1 and 3 selected**.

Multistage Graph Problems

• Definition: A directed acyclic graph (DAG) where vertices are partitioned into $k$ stages $$\displaystyle V_1, V_2, ..., V_k $$. Edges only go from stage $i$ to stage $i+1$. A start vertex $$\displaystyle s \in V_1 $$ and a terminal vertex $$\displaystyle t \in V_k $$. Edge $(i,j)$ has cost $$\displaystyle c_{ij} $$. Find the minimum-cost path from $s$ to $t$.

• DP Approach:

  • Let $$\displaystyle f_i(j) $$ = minimum cost from vertex $j$ in stage $i$ to terminal $t$.

  • Forward Recursion (from $t$ backwards):

$$ f_{k-1}(j) = \min_{k \in \text{succ}(j)} \{ c_{jk} + f_k(k) \}, \quad \text{for } j \in V_{k-1} $$

    Base: $$\displaystyle f_k(t) = 0 $$.

*   **Backward Recursion** (from $s$ forwards):

    Let $$\displaystyle f_i(j) $$ = minimum cost from $s$ to vertex $j$ in stage $i$.

$$ f_{i+1}(k) = \min_{j \in \text{pred}(k)} \{ f_i(j) + c_{jk} \}, \quad \text{for } k \in V_{i+1} $$

    Base: $$\displaystyle f_1(s) = 0 $$.

• Algorithm (Forward): Compute $$\displaystyle f_{k-1}, f_{k-2}, ..., f_1(s) $$ in order.

• Computing Time: $$\displaystyle O(n^2) $$ if graph is dense (each stage has $O(n)$ vertices, each vertex has $O(n)$ outgoing edges). For $k$ stages with $$\displaystyle n_i $$ vertices in stage $i$, time is $$\displaystyle O(\sum_{i=1}^{k-1} n_i \cdot n_{i+1}) $$.

• Applications: Resource allocation, project scheduling, multi-stage decision making.

All-Pairs Shortest Paths: Floyd-Warshall Algorithm

• Problem: Given a weighted directed graph (may have negative weights but no negative cycles), find the shortest path distance between every pair of vertices.

• DP Formulation:

  Let $$\displaystyle d^{(k)}[i][j] $$ = shortest path from $i$ to $j$ using only intermediate vertices from $\{1,2,...,k\}$.

  Recurrence:

$$ d^{(k)}[i][j] = \min\left( d^{(k-1)}[i][j],\ d^{(k-1)}[i][k] + d^{(k-1)}[k][j] \right) $$

Base: $$\displaystyle d^{(0)}[i][j] = \text{weight}(i,j) $$ if edge exists, else $\infty$; $$\displaystyle d^{(0)}[i][i] = 0 $$.

• Algorithm:

  1. Initialize $$\displaystyle D = \text{adjacency matrix} $$ (with $$\displaystyle D[i][i]=0 $$, $$\displaystyle D[i][j]=\infty $$ if no edge).

  2. For $$\displaystyle k = 1 $$ to $n$:

     • For $$\displaystyle i = 1 $$ to $n$:

       • For $$\displaystyle j = 1 $$ to $n$:

         • $$\displaystyle D[i][j] = \min(D[i][j], D[i][k] + D[k][j]) $$.

  3. $D$ contains all-pairs shortest distances.

• Time Complexity: $$\displaystyle O(V^3) $$.

• Space Complexity: $$\displaystyle O(V^2) $$.

• Path Reconstruction: Maintain a predecessor matrix next[i][j]. Update when a shorter path via $k$ is found: next[i][j] = next[i][k].

• Example: Given graph (as in Nov 2023 paper), apply algorithm step-by-step for $$\displaystyle k=1,2,...,n $$.

V. Backtracking

General Method

• Idea: Systematic way to enumerate all possible solutions (or a subset) by exploring a state space tree. It is a depth-first search (DFS) with pruning.

• Key Concepts:

  • State Space Tree: Nodes represent partial solutions (configurations). Root is initial state. Leaves are complete solutions or dead ends.

  • Promising Node: A partial solution that may lead to a feasible complete solution.

  • Non-promising Node: A partial solution that cannot be extended to a feasible solution (pruned).

  • Backtracking: When a node is found non-promising, return (backtrack) to its parent and explore next alternative.

• Algorithm Template:

  
  Backtrack(candidate):
  
      if candidate is a complete solution: output it; return
  
      for each possible next move from candidate:
  
          if move is feasible (satisfies constraints):
  
              apply move
  
              Backtrack(new_candidate)
  
              undo move (backtrack)
  
  

N-Queens Problem

• Problem: Place $N$ queens on an $N \times N$ chessboard such that no two queens attack each other (no two in same row, column, or diagonal).

• Backtracking Approach:

  • Place queens row by row.

  • State: partial placement of queens in rows $1..k$.

  • For row $k+1$, try each column $j$. Check if placing queen at $(k+1, j)$ is safe (no conflict with previously placed queens in columns or diagonals).

  • If safe, place queen and recurse for next row.

  • If no column works in a row, backtrack.

• Pseudocode:

  
  NQueens(k, N, board):  // board[1..N] stores column of queen in row i
  
      if k > N: 
  
          print board; return
  
      for j = 1 to N:
  
          if IsSafe(k, j, board):  // check column j and diagonals for rows 1..k-1
  
              board[k] = j
  
              NQueens(k+1, N, board)
  
              // backtrack: board[k] = 0 (optional)
  
  

• State Space Tree for 4-Queens:

  • Root: empty board.

  • Level 1: Place queen in row1 at col1,2,3,4 → 4 nodes.

  • Level 2: For each, try safe columns in row2. Many become dead ends quickly.

  • Solutions: [2,4,1,3] and [3,1,4,2] (queen positions by row).

  • Tree has many dead ends; backtracking prunes aggressively.

• Complexity: Worst-case $O(N!)$ (since at most $N$ choices per row, but pruning reduces drastically). Practical for $N \le 30$.

Graph Coloring Problem (m-coloring)

• Problem: Given an undirected graph $$\displaystyle G=(V,E) $$ and $m$ colors, assign a color to each vertex such that no two adjacent vertices have the same color. Determine if a valid coloring exists.

• Backtracking Approach:

  • Order vertices (e.g., $$\displaystyle v_1, v_2, ..., v_n $$).

  • State: colors assigned to first $k$ vertices.

  • For vertex $$\displaystyle v_{k+1} $$, try each color $c \in \{1..m\}$. Check if $c$ is not used by any neighbor of $$\displaystyle v_{k+1} $$ that is already colored.

  • If safe, assign color and recurse.

• Pseudocode:

  
  mColoring(k, G, color[1..n]):
  
      if k > n: return true  // all colored
  
      for c = 1 to m:
  
          if color c is safe for vertex k:
  
              color[k] = c
  
              if mColoring(k+1, G, color): return true
  
              color[k] = 0  // backtrack
  
      return false
  
  

• Example: Solve for given graph (e.g., triangle with $$\displaystyle m=2 $$ impossible, $$\displaystyle m=3 $$ possible).

Hamiltonian Cycle Problem

• Problem: Given a graph $$\displaystyle G=(V,E) $$, find a cycle that visits every vertex exactly once and returns to start.

• Backtracking Approach:

  • Start from a vertex (say $$\displaystyle v_0 $$). Maintain a path array path[0..n-1] where path[i] is $i$-th vertex in path.

  • State: current path of length $k$ (vertices path[0..k-1]).

  • For vertex path[k-1], try each neighbor $v$ not yet in path. Add $v$ to path[k], recurse for $k+1$.

  • If $$\displaystyle k = n $$ and there is an edge from path[n-1] to path[0], a Hamiltonian cycle is found.

• Pseudocode:

  
  Hamiltonian(k):
  
      if k == n:
  
          if edge exists between path[k-1] and path[0]: print cycle
  
          else: return
  
      for each vertex v adjacent to path[k-1]:
  
          if v not in path[0..k-1]:
  
              path[k] = v
  
              Hamiltonian(k+1)
  
              // backtrack
  
  

• Example: Apply to a sample graph (e.g., pentagon with diagonals).

VI. Branch and Bound

General Method

• Idea: Systematic exploration of state space tree, but prunes branches that cannot yield a better solution than the best one found so far, using bounding functions.

• Key Concepts:

  • Live Node: A node that has been generated but whose children not yet fully explored.

  • Dead Node: A node that cannot lead to a better solution (pruned).

  • E-node (Expanding Node): A live node that is being explored (its children are generated).

  • Bounding Function: Computes a lower bound (for minimization) or upper bound (for maximization) on the best possible solution achievable from that node.

• Search Strategies:

  • FIFO (Breadth-first): Use queue.

  • LIFO (Depth-first): Use stack.

  • Best-first (Least cost): Use priority queue ordered by bound (most common). Always expand the live node with best bound (smallest lower bound for minimization).

• Comparison with Backtracking:

  • Backtracking: Prunes based on feasibility (whether node can lead to any feasible solution).

  • Branch and Bound: Prunes based on optimality (whether node can lead to a solution better than current best). Also uses bounds to guide search order.

Traveling Salesperson Problem (TSP)

• Problem: Given a complete weighted graph (or distance matrix) of $n$ cities, find the minimum-cost Hamiltonian cycle (tour visiting each city exactly once and returning to start).

• Branch and Bound with Reduction (Matrix Method):

  1. Reduction: For the current cost matrix $C$:

     • Row Reduction: For each row, subtract the minimum element in that row from all elements in the row. Sum of all row minima = $r$.

     • Column Reduction: For each column, subtract the minimum element in that column from all elements in the column. Sum of all column minima = $c$.

     • The reduced matrix has at least one zero in each row/column. The lower bound for any tour extending this partial path is $$\displaystyle LB = \text{parent's LB} + r + c $$.

  2. Branching: Choose an edge $(i,j)$ to include or exclude.

     • To include edge $(i,j)$: Set row $i$ and column $j$ to $\infty$ (since we can't leave $i$ or enter $j$ again). Also set $$\displaystyle C[j][i] = \infty $$ (to prevent immediate return). Reduce matrix, compute new $LB$.

     • To exclude edge $(i,j)$: Set $$\displaystyle C[i][j] = \infty $$. Reduce matrix, compute new $LB$.

  3. Node Selection: Use a priority queue (min-heap) keyed by $LB$. Always expand the node with smallest $LB$.

  4. Termination: When a complete tour (path of length $n$) is found, its cost is the upper bound (best so far). Prune any live node with $LB \ge \text{current best}$. When queue is empty, best found is optimal.

• Example: Given a $4 \times 4$ cost matrix, apply reduction, branch on edges, maintain bounds.

• Complexity: Worst-case exponential, but pruning can be very effective for small $n$ (typically $n \le 20$).

VII. Advanced & Special Topics

Computational Complexity Theory

• Class P: Problems solvable by a deterministic Turing machine in polynomial time (e.g., sorting, shortest path).

• Class NP: Problems for which a solution can be verified in polynomial time by a deterministic Turing machine (or solvable by a non-deterministic TM in poly time). Includes P.

• NP-Complete (NPC):

  • Problems in NP.

  • Every problem in NP can be reduced to it in polynomial time (NP-hard).

  • If any NPC problem has a poly-time algorithm, then P = NP.

  • Examples: SAT, 3-SAT, Clique, Vertex Cover, Hamiltonian Cycle, 0/1 Knapsack (decision version).

• NP-Hard (NPH):

  • Problems at least as hard as the hardest problems in NP.

  • May not be in NP (e.g., optimization versions, undecidable problems).

  • Every NPC problem is NP-hard, but not every NP-hard is NPC.

  • Examples: TSP (optimization), Halting Problem (undecidable).

• Comparison:

• How to Prove NP-Complete:

  1. Show problem is in NP (give polynomial-time verifier).

  2. Take a known NP-complete problem $A$.

  3. Construct a polynomial-time reduction from $A$ to your problem $B$ (transform instance of $A$ to instance of $B$ such that answer is "yes" for $A$ iff "yes" for $B$).

Parallel Algorithms

• Motivation: Speed up computation using multiple processors/cores. Address limitations of sequential algorithms for big data, real-time systems.

• Models: PRAM (Parallel Random Access Machine) – shared memory, synchronous. Variants: CREW (concurrent read, exclusive write), CRCW (concurrent read, concurrent write).

• Key Metrics:

  • Speedup $$\displaystyle S(p) = T(1) / T(p) $$, where $T(p)$ is time on $p$ processors.

  • Efficiency $$\displaystyle E(p) = S(p)/p $$.

  • Work $$\displaystyle W(p) = p \cdot T(p) $$. Ideal: $W(p) \approx T(1)$ (no overhead).

• Examples:

  • Parallel Merge Sort: Divide array into $p$ parts, sort each in parallel ($O((n/p) \log (n/p))$), then merge in parallel ($O(\log p)$ steps with parallel merging). Total $$\displaystyle T(p) = O((n/p) \log n + \log p) $$, speedup near-linear.

  • Parallel Prefix Sum (Scan): Given array $a[0..n-1]$, compute $$\displaystyle s[i] = a[0]+a[1]+...+a[i] $$. Sequential $O(n)$. Parallel: using tree-based approach, $O(\log n)$ time with $O(n)$ work.

• Challenges: Synchronization overhead, load balancing, granularity (task size vs. communication cost), Amdahl's Law (speedup limited by sequential fraction).

Data Stream Algorithms

• Streaming Model: Data arrives as a stream (one or few passes). Limited memory (sublinear in stream length $n$ or in domain size). Often need approximate answers.

• Applications: Network traffic monitoring (heavy hitters), financial analysis (distinct count), streaming services (real-time recommendations, trending topics), sensor networks.

• Example Algorithms:

  • Misra-Gries (Heavy Hitters): Find all items with frequency $$\displaystyle > \frac{n}{k} $$. Maintain at most $k-1$ candidate items with counts. Space $O(k)$.

  • Flajolet-Martin (Distinct Count): Estimate number of distinct elements using bit patterns and hashing. Space $O(\log \log n)$.

  • Count-Min Sketch: Estimate frequency of any item with error bound. Space $O(1/\epsilon \log 1/\delta)$.

• Use in Streaming Services:

  • Recommendation: Track user interactions (clicks, views) in a stream. Use heavy hitter algorithms to find popular items per user segment. Use distinct count to measure catalog diversity.

  • Real-time Analytics: Detect trending topics (heavy hitters in hashtag streams), monitor system health (error rates via count-min sketches), anomaly detection (sudden spikes in metrics).

Logic Optimization

• Goal: Minimize the cost (e.g., number of gates, delay) of a Boolean circuit implementing a given Boolean function.

• Boolean Function: $$\displaystyle f(x_1, x_2, ..., x_n) : \{0,1\}^n \to \{0,1\} $$.

• Methods:

  1. Karnaugh Map (K-map):

     • Graphical method for up to 4-6 variables.

     • Group adjacent 1s (or 0s for POS) in powers of 2 (1,2,4,8,...).

     • Each group gives a prime implicant (product term).

     • Select essential prime implicants and cover remaining minterms with minimal set (Petrick's method).

     • Example: Minimize $$\displaystyle f(A,B,C,D) = \sum m(0,2,5,7,8,10,13,15) $$.

  2. Quine-McCluskey (Tabular) Method:

     • Systematic for any number of variables.

     • Step 1: List all minterms (binary). Combine minterms differing in one bit to form prime implicants (with dash -).

     • Step 2: Repeat combining until no more combinations.

     • Step 3: Construct prime implicant chart (rows: prime implicants, columns: minterms).

     • Step 4: Find minimal cover using essential prime implicants and solving set cover problem (Petrick's method).

• Relevance to Algorithm Design: Efficient evaluation of complex Boolean conditions (e.g., in compilers, circuit design, rule-based systems). Simplified logic leads to faster conditional checks and smaller hardware.

B-Trees

• Definition: A self-balancing m-way search tree (each node can have up to $m$ children, $m \ge 3$). All leaves at same depth. Used extensively in databases and file systems (disk-based).

• Structure:

  • Node contains up to $m-1$ keys in sorted order: $$\displaystyle k_1 < k_2 < ... < k_{t} $$ ($t \le m-1$).

  • Node with $t$ keys has $t+1$ children (pointers).

  • For any node, keys separate the ranges of its children: $$\displaystyle c_0 < k_1 < c_1 < k_2 < ... < k_t < c_t $$.

  • Height Balance: All leaves at same level.

• Creation/Insertion:

  1. Search for leaf where key should go.

  2. If leaf has $$\displaystyle < m-1 $$ keys, insert key in sorted order.

  3. If leaf is full ($m-1$ keys), split it:

     • Median key $$\displaystyle k_{\lceil m/2 \rceil} $$ moves up to parent.

     • Left half keys stay in left node, right half in new right node.

     • If parent is full, split recursively up to root (may increase tree height).

• Advantages:

  • Balanced: Guarantees $$\displaystyle O(\log_m n) $$ height (very shallow, $m$ large).

  • Optimized for Block Access: Node size typically matches disk block size. One disk I/O per node access.

  • Efficient Inserts/Deletes: Splitting/merging maintains balance.

  • Widely Used: In databases (B+ trees, variant), filesystems (NTFS, ext4), etc.

Horner's Algorithm for Polynomial Evaluation

• Problem: Evaluate polynomial $$\displaystyle P(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n $$ at a given $x$.

• Naive Method: Compute each term $$\displaystyle a_i x^i $$ separately (using $i$ multiplications) and sum. Total multiplications: $$\displaystyle 1+2+...+n = O(n^2) $$.

• Horner's Method (Nested Multiplication):

$$ P(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_{n-1} + x a_n)...)) $$

Evaluate from innermost out.

• Algorithm:

  
  Horner(P[0..n], x):
  
      result = P[n]  // a_n
  
      for i = n-1 downto 0:
  
          result = result * x + P[i]
  
      return result
  
  

• Example: $$\displaystyle P(x) = 2x^3 - 6x^2 + 2x - 1 $$ at $$\displaystyle x=3 $$.

  • Coefficients: $$\displaystyle a_3=2, a_2=-6, a_1=2, a_0=-1 $$.

  • Steps: result=2; result=23 + (-6)=0; result=03+2=2; result=2*3+(-1)=5. So $$\displaystyle P(3)=5 $$.

• Time Complexity: $O(n)$ multiplications and additions. Optimal for polynomial evaluation.

• Advantages: Minimal operations, numerically stable (fewer operations reduce rounding errors).

Space Complexity

• Definition: Amount of memory auxiliary (extra beyond input) used by an algorithm as a function of input size $n$.

• Components:

  • Auxiliary Space: Temporary space used by algorithm (e.g., recursion stack, extra arrays).

  • Input Space: Space for input itself (usually not counted in auxiliary space).

• Analysis:

  • Iterative algorithms: Usually $O(1)$ auxiliary space (fixed number of variables).

  • Recursive algorithms: Space = $O(\text{recursion depth} \times \text{space per call})$.

    • Example: Recursive Fibonacci (naive) has recursion depth $n$, each call constant space → $O(n)$ space.

    • Recursive binary search: depth $O(\log n)$ → $O(\log n)$ space.

• Trade-off: Sometimes more space (e.g., DP table) reduces time (memoization/tabulation).

• Example: Compare iterative vs. recursive Fibonacci. Iterative uses $O(1)$ space, recursive uses $O(n)$ stack space.