Analysis and Design of Algorithm (IT-403) - Unit 2 Short Notes

UNIT 2: Analysis and Design of Algorithm - Short Notes

I. Fundamentals of Algorithm Analysis

Algorithm Design and Analysis Process

The systematic approach involves:

1. Problem Definition: Precisely state the problem, inputs, and expected outputs.

2. Algorithm Specification: Choose/design an algorithm (pseudocode/flowchart).

3. Correctness Proof: Verify the algorithm solves the problem for all valid inputs.

4. Complexity Analysis: Evaluate time/space requirements using asymptotic notations.

5. Implementation: Code the algorithm in a programming language.

Flow Chart Representation: Uses standard symbols (oval for start/end, parallelogram for I/O, rectangle for process, diamond for decision, arrows for flow).

Asymptotic Notations

Used to describe the limiting behavior of a function.

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

  • Example: $$\displaystyle 3n^2 + 2n + 1 = O(n^2) $$.

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

  • Example: $$\displaystyle 3n^2 + 2n + 1 = \Omega(n^2) $$.

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

  • Example: $$\displaystyle 3n^2 + 2n + 1 = \Theta(n^2) $$.

Time Complexity Analysis

• Worst-Case: Maximum time over all inputs of size $n$. Provides an upper guarantee. Relevant for real-time systems, security (e.g., password hashing).

• Average-Case: Expected time over all inputs, assuming a probability distribution. Relevant for algorithms used on "typical" data (e.g., Quick Sort).

• Best-Case: Minimum time over all inputs of size $n$. Often trivial (e.g., finding an element at first index). Rarely used for guarantees.

Trade-off: Sacrifice readability for optimization only when:

1. Profiling identifies a critical bottleneck.

2. The optimization is well-documented.

3. The performance gain is significant and necessary for the context.

Never sacrifice readability for premature or unproven optimization.

Recurrence Relations

Formation: Express $T(n)$ in terms of $T(k)$ for $$\displaystyle k < n $$.

• Example (Binary Search): $$\displaystyle T(n) = T(n/2) + O(1) $$.

Solving Methods:

1. Substitution Method: Guess a solution, prove by induction.

2. Recursion Tree Method: Visualize costs per level, sum them.

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}) $$, 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 regularity condition holds, then $$\displaystyle T(n) = \Theta(f(n)) $$.

Examples:

• $$\displaystyle T(n) = n + T(n/10) + T(7n/5) $$: Cannot use Master Theorem (subproblems are unequal). Use recursion tree or substitution.

• $$\displaystyle T(n) = 7T(n/2) + n^2 $$: Master Theorem Case 2 ($$\displaystyle f(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81}) $$). $$\displaystyle \therefore T(n) = \Theta(n^{\log_2 7}) $$.

Lower Bound Theory

• Decision Trees: Model comparisons as binary trees. Each leaf is a permutation. Height $h$ gives comparison-based lower bound: $$\displaystyle h \ge \log_2(n!) = \Omega(n \log n) $$ for sorting.

  • Application: Proves $\Omega(n \log n)$ lower bound for comparison-based sorting.

• Algebraic Problems: E.g., lower bound for matrix multiplication is $$\displaystyle \Omega(n^2) $$ (must read all $$\displaystyle n^2 $$ inputs).

Sorting Algorithms: Stability

Stability: Equal elements retain relative order after sorting.

• Stable: Merge Sort, Insertion Sort, Bubble Sort.

• Unstable: Quick Sort, Heap Sort, Selection Sort (naive implementation).

  • Reason: Quick Sort's partitioning swaps non-adjacent elements; Heap Sort's heapify can swap equal elements across subheaps.

Importance: Crucial when sorting by multiple keys (e.g., sort by name, then by grade; stable sort preserves name order within same grade).

II. Divide and Conquer Paradigm

General Method & Control Abstraction

Steps:

1. Divide: Split problem into smaller subproblems.

2. Conquer: Solve subproblems recursively.

3. Combine: Merge subproblem solutions.

Recurrence Formulation: $$\displaystyle T(n) = a \cdot T(n/b) + f(n) $$, where $a$ = number of subproblems, $n/b$ = size of each, $f(n)$ = divide/combine cost.

Binary Search

• Algorithm: On sorted array, compare target with middle element; recurse on left/right half.

• Recurrence: $$\displaystyle T(n) = T(n/2) + O(1) $$.

• Complexity: $$\displaystyle T(n) = O(\log n) $$ (by Master Theorem or recursion tree).

Merge Sort

• Algorithm:

  1. If $n \le 1$, return.

  2. Recursively sort left and right halves.

  3. Merge two sorted halves in $O(n)$ time.

• Complexity: $$\displaystyle T(n) = 2T(n/2) + O(n) \Rightarrow T(n) = O(n \log n) $$.

• Stability: Yes (merge step preserves order of equal elements).

• Example: Sort {23, 11, 5, 15, 68, 31, 4, 17} → {4, 5, 11, 15, 17, 23, 31, 68}.

Quick Sort

• Algorithm:

  1. Partition array around a pivot (Lomuto/Hoare scheme).

  2. Recursively sort left and right partitions.

• Partition (Lomuto):

  
  pivot = A[high]; i = low-1;
  
  for j = low to high-1:
  
      if A[j] <= pivot: i++; swap A[i] and A[j];
  
  swap A[i+1] and A[high]; return i+1;
  
  

• Complexity:

  • Average: $O(n \log n)$ (balanced partitions).

  • Worst: $$\displaystyle O(n^2) $$ (highly unbalanced, e.g., sorted input with first/last pivot).

• Avoiding Worst-Case: Use randomized pivot or median-of-three.

• Example: Sort {20, 35, 10, 16, 54, 21, 25} (pivot=25):

  • After partition: {20, 10, 16, 21, 25, 54, 35}

  • Recurse on {20,10,16,21} and {54,35}.

Strassen's Matrix Multiplication

• Algorithm: For $2 \times 2$ matrices, uses 7 recursive multiplications instead of 8.

  • Compute 7 products ($$\displaystyle P_1 $$ to $$\displaystyle P_7 $$) using combinations of submatrices.

  • Combine to get result quadrants.

• Complexity: $$\displaystyle T(n) = 7T(n/2) + O(n^2) \Rightarrow T(n) = O(n^{\log_2 7}) \approx O(n^{2.81}) $$.

• Vs Conventional: $$\displaystyle O(n^3) $$. Strassen's is faster for large $n$ but has larger constant factors and numerical instability.

• Applicability: Only for square matrices of size $$\displaystyle 2^k $$. Padding required otherwise.

Max/Min in Array (Divide & Conquer)

• Algorithm:

  • If $$\displaystyle n=1 $$, return (element, element).

  • If $$\displaystyle n=2 $$, compare and return (min, max).

  • Else, split array, get (minL, maxL) and (minR, maxR). Return (min(minL,minR), max(maxL,maxR)).

• Recurrence: $$\displaystyle T(n) = 2T(n/2) + 2 $$ (2 comparisons to merge).

• Complexity: $$\displaystyle T(n) = O(n) $$ (better than naive $2n-2$ comparisons? Actually same order, but fewer comparisons: $\approx 1.5n$ vs $2n$).

III. Greedy Algorithms

Greedy Choice Property & Optimal Substructure

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

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

• Both Required: To prove a greedy algorithm is correct, prove it satisfies both properties.

Job Sequencing with Deadlines

• Problem: Maximize profit with jobs having deadlines (1 unit time each).

• Algorithm:

  1. Sort jobs by decreasing profit.

  2. Initialize array slot[1..max_deadline] as empty.

  3. For each job in sorted order: place it in the latest available slot before its deadline.

• Example (from Jun 2024/2023): Jobs: (P:100,10,15,27), (D:2,1,2,1)

  • Sorted by profit: J1(P100,D2), J4(P27,D1), J3(P15,D2), J2(P10,D1).

  • Schedule: J1 at slot 2, J4 at slot 1. Max Profit = 127.

Fractional Knapsack Problem

• Problem: Maximize value with fractional items allowed.

• Algorithm:

  1. Compute value/weight ratio for each item.

  2. Sort items by decreasing ratio.

  3. Take items in order until knapsack full; last item may be taken fractionally.

• Example (from Jun 2024): n=7, W=15, P=(10,5,15,7,6,18,3), w=(2,3,5,7,1,4,1)

  • Ratios: 5, 1.67, 3, 1, 6, 4.5, 3.

  • Sorted: item5(6/1), item6(18/4), item1(10/2), item7(3/1), item3(15/5), item2(5/3), item4(7/7).

  • Take: 1 unit of 5 (W=1, V=6), 4 units of 6 (W=5, V=18), 2 units of 1 (W=7, V=10), 1 unit of 7 (W=8, V=3), 5 units of 3 (W=13, V=15), 2 units of 2 (W=15, V=3.33). Total Value = 55.33.

Huffman Coding

• Problem: Construct optimal prefix-free binary codes for symbols with given probabilities.

• Algorithm:

  1. Create min-heap (or sorted list) of nodes (symbol, prob).

  2. While heap size > 1:

     • Extract two nodes with smallest probabilities.

     • Create new internal node with prob = sum, left/right children.

     • Insert new node into heap.

  3. Assign 0/1 to left/right branches. Codes are root-to-leaf paths.

• Example (from Jun 2025): Probabilities: a(0.07), b(0.09), c(0.12), d(0.22), e(0.23), f(0.27).

  • DiagramCANVAS: Huffman tree construction steps: combine a(0.07)+b(0.09)=0.16; combine c(0.12)+0.16=0.28; combine d(0.22)+e(0.23)=0.45; combine 0.28+0.45=0.73; combine 0.73+f(0.27)=1.0. Final tree: f:0, d:10, e:110, 0.28-node:1110, c:11110, ab-node:11111 (a:0, b:1).

  • Average Code Length = $$\displaystyle \sum p_i \cdot l_i $$ = $$\displaystyle 0.27\times1 + 0.22\times2 + 0.23\times3 + 0.12\times4 + 0.09\times5 + 0.07\times5 $$ = 2.42 bits/symbol.

Minimum Spanning Tree (MST)

• Definition: Tree connecting all vertices with minimum total edge weight.

• Kruskal's Algorithm:

  1. Sort all edges by increasing weight.

  2. Initialize MST as empty, use Union-Find (Disjoint Set).

  3. For each edge in sorted order: if it connects two different components (find-set(u) ≠ find-set(v)), add to MST and union the sets.

  4. Stop when MST has $V-1$ edges.

  • Complexity: $O(E \log E)$ (sorting dominates).

• Prim's Algorithm:

  1. Start from arbitrary vertex. Maintain a min-priority queue (key = min edge weight to tree).

  2. While queue not empty: extract-min vertex $u$, add to MST. For each neighbor $v$ not in MST, if weight(u,v) < key[v], update key[v] and parent.

  • Complexity: $O(E \log V)$ with binary heap.

• Uniqueness with Distinct Weights: Proof: Suppose two different MSTs $$\displaystyle T_1, T_2 $$. Consider the smallest-weight edge $e$ that differs. $e$ is in $$\displaystyle T_1 $$ but not $$\displaystyle T_2 $$. Adding $e$ to $$\displaystyle T_2 $$ creates a cycle. In that cycle, there must be an edge $e'$ with weight > weight($e$) (since $e$ is smallest differing). Replacing $e'$ with $e$ yields a spanning tree lighter than $$\displaystyle T_2 $$, contradiction. Example: Graph with edges weights all distinct → unique MST.

Optimal Merge Patterns

• Problem: Merge $n$ sorted files (sizes $$\displaystyle l_1, l_2, ..., l_n $$) with minimal total comparisons (or I/O operations).

• Greedy Solution: Always merge the two smallest files first. Equivalent to constructing a Huffman tree where file sizes are frequencies.

• Example: Files of lengths 15, 10, 20, 25, 30.

  • Merge 10+15=25 (cost 25), now have 20,25,25,30.

  • Merge 20+25=45 (cost 45), now have 25,30,45.

  • Merge 25+30=55 (cost 55), now have 45,55.

  • Merge 45+55=100 (cost 100). Total Cost = 225.

IV. Dynamic Programming

Principle of Optimality & Overlapping Subproblems

• Principle of Optimality: An optimal solution to the problem contains within it optimal solutions to subproblems.

• Overlapping Subproblems: The recursive solution breaks the problem into subproblems that are repeatedly solved. DP stores solutions to avoid recomputation (memoization/tabulation).

0/1 Knapsack Problem

• Problem: Maximize total value with items having value $$\displaystyle p_i $$, weight $$\displaystyle w_i $$, capacity $W$. Each item taken or not (0/1).

• DP Table: $DP[i][w]$ = max value 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(DP[i-1][w],\ p_i + DP[i-1][w-w_i]) & \text{otherwise} \end{cases} $$

• Algorithm:

  1. Build $DP[n+1][W+1]$ table.

  2. $DP[n][W]$ is answer.

  3. Backtrack to find selected items.

• Example (from Jun 2023): P=(11,21,31,33), W=(2,12,23,15), C=42, n=4.

  • DiagramCANVAS: DP table 5x43. Row1: all 0. Row2: w>=2:11. Row3: w>=12: max(11,21)=21. Row4: w>=23: max(21, 31+DP[2][0]=31)=31. Row5: w>=15: max(31, 33+DP[3][27]=33+31? Wait, w-w4=27, DP[3][27] from row3 col27 is 21? Actually need full table. Final DP[4][42] = 11+31=42? Let's compute: items 1 and 3: w=2+23=25, v=11+31=42. That fits. So answer=42.

Reliability Design Problem

• Problem: Design a multistage system (e.g., 3 stages) with device types per stage. Each type has cost $$\displaystyle c_{ij} $$ and reliability $$\displaystyle r_{ij} $$. Maximize total reliability $$\displaystyle \prod r_{ij} $$ subject to total cost $\le C$.

• DP Formulation: $R[i][c]$ = max reliability for first $i$ stages with cost $c$.

  • $$\displaystyle R[0][c] = 1 $$ for all $c$.

  • $$\displaystyle R[i][c] = \max_{j} \{ r_{ij} \times R[i-1][c - c_{ij}] \} $$ for all device choices $j$ in stage $i$ where $$\displaystyle c_{ij} \le c $$.

• Example (from Jun 2023/Dec 2024): 3 stages, costs: d1=30, d2=15, d3=20; reliabilities: 0.9, 0.8, 0.5; total cost $\le 105$.

  • Stage 1: only d1 (cost30, rel0.9).

  • Stage 2: d2 (15,0.8) or d2? Actually only one device per stage? Typically one device per stage. So we choose one type per stage.

  • DP: For stage 1: R[1][c] = 0.9 if c>=30 else 0.

  • Stage 2: For each c, try d2 (cost15): R[2][c] = max(0.8 * R[1][c-15]).

  • Stage 3: For each c, try d3 (cost20): R[3][c] = max(0.5 * R[2][c-20]).

  • Compute for c=105: R[3][105] = 0.5 * R[2][85]. R[2][85] = 0.8 * R[1][70] = 0.80.9=0.72. So R[3][105]=0.36. But we can also use multiple devices in parallel per stage? The problem says "multistage system design", often allows parallel devices per stage. Then it's more complex: for each stage, we choose number of devices of each type. But given data, likely one device per stage. So max reliability = 0.90.8*0.5=0.36 at cost 30+15+20=65. With remaining cost 40, we could add redundancy? If allowed, we could add another device in a stage (parallel). But typical formulation: each stage has one device, choose type. So answer is 0.36.

Multistage Graph Problem

• Problem: Find shortest path from source (stage 1) to sink (stage k) in a directed acyclic multistage graph.

• DP Approach (Backward):

  • Let $C[i][j]$ = cost from vertex $j$ in stage $i$ to sink.

  • Recurrence: $$\displaystyle C[i][j] = \min_{k \in \text{adj}(j)} \{ \text{cost}(j,k) + C[i+1][k] \} $$.

  • Base: $$\displaystyle C[k][\text{sink}] = 0 $$.

• Algorithm: Compute $C[i][j]$ backward from stage $k-1$ to 1.

• Time Complexity: $O(V+E)$ (each edge examined once).

• Example: Given graph with stages, compute costs backward.

All-Pairs Shortest Paths

• Floyd-Warshall Algorithm:

  • DP: Let $$\displaystyle D^k[i][j] $$ = shortest path from $i$ to $j$ using vertices $\{1,2,...,k\}$ as intermediates.

  • Recurrence:

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

*   **Algorithm**: Initialize $$\displaystyle D^0 $$ = adjacency matrix (0 for diagonal, $\infty$ for no edge). For $$\displaystyle k=1 $$ to $n$: update all $i,j$.

*   **Complexity**: $$\displaystyle O(n^3) $$.

*   **Example**: Given graph, compute $$\displaystyle D^1, D^2, D^3 $$ matrices.

• Transitive Closure: Use Floyd-Warshall with boolean algebra (OR for min, AND for +). Or Warshall's Algorithm specifically for closure.

V. Backtracking

Concept & State-Space Tree

• Systematic Exploration: Build solution incrementally, abandoning (backtracking) a path as soon as it is determined cannot lead to a valid solution.

• State-Space Tree: Nodes represent partial solutions. Root is initial state. Leaves are complete solutions or dead ends. Internal nodes are promising/unpromising.

• Pruning: Use constraints to cut off branches early.

Subset Sum Problem

• Problem: Given set $$\displaystyle S = \{s_1, s_2, ..., s_n\} $$ and target $X$, find subset summing to $X$.

• Algorithm (Recursive):

  
  subset_sum(i, current_sum):
  
      if current_sum == X: return true (solution found)
  
      if i > n or current_sum > X: return false
  
      // Include s_i
  
      if subset_sum(i+1, current_sum + s_i): return true
  
      // Exclude s_i
  
      return subset_sum(i+1, current_sum)
  
  

• Example (from Jun 2025): $$\displaystyle S=\{1,3,4,5\}, X=8 $$.

  • State-space tree: root (0,1). Branch include 1 → (1,2). Include 3 → (4,3). Include 4 → (8,4) solution. Also: include 1, exclude 3, include 4, include 5 → (10,4) prune. Exclude 1, include 3, include 5 → (8,3) solution.

n-Queens Problem

• Problem: Place $n$ queens on $n \times n$ chessboard so no two attack.

• Backtracking: Place queens row by row. For row $i$, try each column $j$. Check if safe (no queen in same column, or diagonals). If safe, place and recurse to row $i+1$. If no column works, backtrack.

• 4-Queens Solutions: [2,4,1,3] and [3,1,4,2] (1-indexed columns per row).

• State-Space Tree: Depth $n$, branching factor up to $n$.

Hamiltonian Cycle Problem

• Problem: Find cycle visiting each vertex exactly once in an undirected graph.

• Backtracking:

  1. Start at vertex $$\displaystyle v_0 $$. Path = [v0].

  2. For each neighbor $u$ of last vertex in path:

     • If $u$ not in path and (if $$\displaystyle u=v_0 $$ only when path length = $n$), add $u$ and recurse.

  3. If path length = $n+1$ and last vertex connects to $$\displaystyle v_0 $$, solution found.

• Example: Given graph, construct tree exploring paths.

Graph Coloring (m-coloring)

• Problem: Color graph vertices with at most $m$ colors so adjacent vertices have different colors.

• Algorithm:

  
  color(v, m):
  
      if v > n: return true (all colored)
  
      for c=1 to m:
  
          if safe(v,c): // no neighbor has color c
  
              assign color[v]=c
  
              if color(v+1, m): return true
  
              unassign color[v] // backtrack
  
      return false
  
  

• Example: Given graph and $$\displaystyle m=3 $$, try colors sequentially.

VI. Branch and Bound

Concept & Reduction Method

• Idea: Systematically enumerate candidate solutions (state-space tree), but prune branches whose best possible solution is worse than current best.

• Cost Matrix Reduction (for TSP):

  1. Row Reduction: Subtract row minimum from each row.

  2. Column Reduction: Subtract column minimum from each column.

  3. Reduced Cost = sum of all subtractions. Any tour has cost $\ge$ reduced cost.

• Bounding Function: For a node (partial path), compute lower bound on completing tour (e.g., reduced cost + cost of partial path + min outgoing from last vertex + min incoming to start).

• Node Branching: From a node, create children by extending path to each unvisited vertex.

Traveling Salesman Problem (TSP)

• Branch and Bound:

  1. Start with root node (empty path, reduced matrix, bound = reduced cost).

  2. Use priority queue (min-heap) ordered by bound.

  3. Expand node with smallest bound. For each possible next city $j$:

     • Create child node: path extended to $j$.

     • Set matrix: row of current city and column of $j$ to $\infty$ (avoid reuse). Reduce matrix again.

     • Child bound = parent bound + cost(current,j) + new reduced cost.

  4. If child path is complete tour, update best cost. Else, insert child in queue.

  5. Prune nodes with bound $\ge$ current best.

• Nearest Neighbor Approximation:

  1. Start at arbitrary city.

  2. Repeatedly go to nearest unvisited city.

  3. Return to start at end.

  • Accuracy Ratio = (Cost of NN tour) / (Cost of optimal tour). Always $\le \log n$? Actually worst-case ratio can be $O(\log n)$ for metric TSP, but unbounded for general TSP.

• Example (from Dec 2024): Given cost matrix, apply reduction and branching.

VII. Graph Algorithms

Breadth-First Search (BFS)

• Algorithm (Queue-based):

  
  BFS(G, s):
  
      for each vertex v: color[v]=WHITE, d[v]=∞, π[v]=NIL
  
      color[s]=GRAY; d[s]=0; π[s]=NIL; Q.enqueue(s)
  
      while Q not empty:
  
          u = Q.dequeue()
  
          for each v adjacent to u:
  
              if color[v]==WHITE:
  
                  color[v]=GRAY; d[v]=d[u]+1; π[v]=u; Q.enqueue(v)
  
          color[u]=BLACK
  
  

• Applications: Shortest path in unweighted graph, connectivity, bipartite test.

• Complexity: $O(V+E)$.

Depth-First Search (DFS)

• Algorithm (Recursive/Stack-based):

  
  DFS(G):
  
      for each vertex u: color[u]=WHITE; π[u]=NIL
  
      time=0
  
      for each vertex u:
  
          if color[u]==WHITE: DFS-Visit(u)
  
  DFS-Visit(u):
  
      color[u]=GRAY; time++; d[u]=time
  
      for each v adjacent to u:
  
          if color[v]==WHITE: π[v]=u; DFS-Visit(v)
  
      color[u]=BLACK; time++; f[u]=time
  
  

• Applications: Topological sort, connectivity, cycle detection, strongly connected components.

• Complexity: $O(V+E)$.

BFS vs DFS:

Topological Sorting

• For Directed Acyclic Graphs (DAGs) only.

• Algorithm using DFS:

  1. Run DFS, record finish times $f[u]$.

  2. Output vertices in decreasing order of finish times.

• Example: Given DAG, perform DFS and list vertices by descending $f$.

Single-Source Shortest Path (Dijkstra)

• Problem: Non-negative edge weights.

• Greedy Algorithm:

  
  Dijkstra(G, s):
  
      for each vertex v: d[v]=∞; π[v]=NIL; S=∅
  
      d[s]=0; Q = min-priority queue keyed by d
  
      while Q not empty:
  
          u = Extract-Min(Q); S = S ∪ {u}
  
          for each v adjacent to u:
  
              if d[v] > d[u] + w(u,v):
  
                  d[v] = d[u] + w(u,v); π[v] = u; Decrease-Key(Q,v)
  
  

• Complexity: $O((V+E)\log V)$ with binary heap.

• Example: Apply to given graph, show $d[]$ updates.

VIII. Tree and Heap Data Structures

Binary Trees

• Traversals:

  • Preorder: Root → Left → Right.

  • Inorder: Left → Root → Right (gives sorted order for BST).

  • Postorder: Left → Right → Root.

• Construct from Inorder & Preorder:

  1. First in preorder is root.

  2. Find root in inorder → left/right subtrees.

  3. Recurse on left/right inorder and corresponding preorder segments.

• Example (from Jun 2022): Inorder: B C A E G D H F I J; Preorder: A B C D E G F H I J.

  • Root = A. Inorder left: B C; right: E G D H F I J.

  • Preorder left: B C; right: D E G F H I J.

  • Recurse: B is root of left subtree (preorder B, inorder B C → B right child C). Right subtree: root D (preorder D, inorder E G D H F I J → left: E G, right: H F I J). Continue.

  • Postorder: C B E G H I F J D A.

Binary Search Trees (BST)

• Operations:

  • Search: $O(h)$ time. Start at root, go left/right based on comparison.

  • Insertion: Search for null position, insert as leaf.

  • Deletion:

    1. If leaf: remove.

    2. If one child: replace with child.

    3. If two children: find inorder successor (min in right subtree), copy its value, delete successor (which has at most one child).

• Height:

  • Average (random): $O(\log n)$.

  • Worst (sorted input): $O(n)$.

AVL Trees

• Balance Factor (BF): $$\displaystyle BF(v) = \text{height(left)} - \text{height(right)} $$. Must be in $\{-1,0,1\}$.

• Rotations (single for LL/RR, double for LR/RL):

  • LL (right rotate at unbalanced node): BF becomes 0,0.

  • RR (left rotate).

  • LR (left rotate on left child, then right rotate on node).

  • RL (right rotate on right child, then left rotate on node).

• Insertion: Insert as BST, update heights on path, check BF, perform rotations if $$\displaystyle |BF|>1 $$.

• Deletion: Similar, may require up to $O(\log n)$ rotations.

B-Trees

• Order $m$: Each node has at most $m$ children, at least $\lceil m/2 \rceil$ children (except root), at most $m-1$ keys, at least $\lceil m/2 \rceil -1$ keys.

• Structure: Keys in sorted order, $k$ keys → $k+1$ children.

• Insertion:

  1. Search leaf where key should go.

  2. Insert key in leaf (sorted). If leaf overflows ($m$ keys), split:

     • Middle key moves up to parent.

     • Left half becomes left child, right half becomes right child.

     • If parent overflows, split recursively.

• Deletion Cases:

  1. Key in leaf: Remove directly. If underflow ($$\displaystyle <\lceil m/2 \rceil -1 $$ keys), borrow from sibling or merge with sibling.

  2. Key in internal node: Replace with predecessor (max in left subtree) or successor (min in right subtree), then delete that key from leaf (reduces to case 1).

• Example: Insert sequence into B-tree of order 5.

2-3 Trees

• Nodes:

  • 2-node: 1 key, 2 children.

  • 3-node: 2 keys, 3 children.

• Properties: All leaves at same level. Nodes never empty.

• Insertion:

  • Find leaf. Insert key.

  • If 2-node → becomes 3-node.

  • If 3-node → split: middle key moves up to parent (may cause parent to split recursively).

• Deletion: More complex, may involve merging/borrowing.

Binomial Heaps

• Properties:

  • Collection of binomial trees (like B-tree but order $k$ has $$\displaystyle 2^k $$ nodes).

  • Each tree satisfies min-heap property.

  • At most one tree of each order $k$.

  • Roots linked in increasing order of degree.

• Union Operation:

  1. Merge two heaps' root lists by degree (like binary addition).

  2. Scan merged list: if two trees have same degree, link (make one child of other, increase degree).

  3. Repeat until no two trees have same degree.

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

• Find Minimum Key:

  • Scan root list (at most $\log n + 1$ roots), find min.

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

Heap Sort

• Algorithm:

  1. Build Max-Heap from array (heapify bottom-up, $O(n)$).

  2. For $$\displaystyle i = n $$ downto 2:

     • Swap $A[1]$ (max) with $A[i]$.

     • Heapify root on heap of size $i-1$.

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

• In-place?: Yes (uses same array).

• Stable?: No (swaps can change order of equal elements).

IX. Advanced Topics

Complexity Classes

• P: Problems solvable in polynomial time by a deterministic Turing machine.

  • Examples: Sorting, shortest path, MST.

• NP: Problems verifiable in polynomial time (solution can be checked quickly), or solvable by nondeterministic TM in polynomial time.

  • Examples: TSP (decision version), Boolean SAT.

• NP-Hard: At least as hard as any NP problem. If $X$ is NP-Hard, every NP problem reduces to $X$ in polynomial time. May not be in NP.

  • Examples: Optimization version of TSP (find min tour), Halting Problem.

• NP-Complete: In NP and NP-Hard.

  • Examples: SAT, 3-SAT, Clique, Vertex Cover, Subset Sum.

• Relationship:

  
  P ⊆ NP ⊆ NP-Hard
  
  NP-Complete = NP ∩ NP-Hard
  
  

  • Open Problem: Is $$\displaystyle P = NP $$?

Approximation Algorithms

• Concept: For NP-Hard optimization problems, find near-optimal solutions quickly.

• Performance Ratio $\rho$: $\rho \ge 1$ such that $$\displaystyle \frac{\text{cost of solution}}{\text{optimal cost}} \le \rho $$ (for minimization) or $\ge 1/\rho$ for maximization.

• Examples:

  • TSP (Metric): Nearest Neighbor has $$\displaystyle \rho = O(\log n) $$. Christofides algorithm has $$\displaystyle \rho = 1.5 $$.

  • Knapsack (Fractional): Greedy is optimal ($$\displaystyle \rho=1 $$). For 0/1, greedy by profit/weight has $$\displaystyle \rho=2 $$.

Data Stream Algorithms

• Constraint: Data arrives as stream, limited memory (sublinear in $n$).

• Examples:

  • Frequent Items (Misra-Gries): Find all items with frequency $$\displaystyle > n/k $$. Use $k-1$ counters. Accuracy: Guarantees no false positives, may have false negatives.

  • Quantiles: Approximate median/percentiles using random sampling or histograms.

Data Transfer Optimization

• Problems: Minimize cost/time in network data transfer (e.g., file distribution, multicast).

• Algorithms: Often use minimum spanning tree (for broadcast) or Steiner tree (NP-Hard, approximated). Multicommodity flow for multiple sources/destinations.

Logic Optimization

• Goal: Minimize Boolean function (fewest gates/transistors).

• Karnaugh Maps (K-maps): Graphical method for up to 4-5 variables. Group adjacent 1s to find prime implicants.

• Quine-McCluskey Method: Tabular systematic method for many variables. Steps: find minterms, combine to prime implicants, find essential primes, use Petrick's method for remaining.

Parallel Algorithms

• Design Paradigms: Divide & conquer, pointer jumping, list ranking.

• Complexity Analysis: Work $$\displaystyle T_1 $$ (sequential time) vs Depth $$\displaystyle T_\infty $$ (critical path length). Cost = $$\displaystyle p \cdot T_p $$ (should be $$\displaystyle \approx T_1 $$ for efficiency).

• Example: Parallel Prefix Sum (Scan): $O(\log n)$ depth, $O(n)$ work. Used in many parallel algorithms.

END OF UNIT 2 NOTES