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

UNIT 1: Analysis and Design of Algorithm – Short Notes

0. Algorithm Design and Analysis Process

Steps:

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

2. Algorithm Design: Develop a step-by-step procedure (pseudo-code) to solve the problem.

3. Analysis: Determine the algorithm's efficiency (time/space complexity) using asymptotic notations.

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

5. Testing & Verification: Test with various inputs to ensure correctness and performance.

Flow Chart Representation:

[!TIP] Exam Focus: Be prepared to draw and explain this flowchart. The feedback loop from Analysis to Design is crucial for iterative improvement.

I. Fundamentals of Algorithm Analysis

Asymptotic Notations (Big O, Big Ω, Big Θ)

Definitions:

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

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

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

Properties:

• Transitivity, Reflexivity, Symmetry (for Θ), and Combination rules.

• $O$-notation is most common for worst-case analysis.

Proving Assertions (Using Definitions):

• i) $$\displaystyle \frac{n(n-1)}{2} = \Theta(n^2) $$

  • Proof: $$\displaystyle \frac{n^2 - n}{2} \leq \frac{n^2}{2} $$ for $n \geq 1$ → $$\displaystyle O(n^2) $$. Also, $$\displaystyle \frac{n^2 - n}{2} \geq \frac{n^2}{4} $$ for $n \geq 2$ → $$\displaystyle \Omega(n^2) $$.

• ii) $$\displaystyle 6 \cdot 2^n + n^2 = O(2^n) $$

  • Proof: $$\displaystyle 6 \cdot 2^n + n^2 \leq 7 \cdot 2^n $$ for $$\displaystyle n \geq n_0 $$ (e.g., $$\displaystyle n_0=4 $$).

• iii) $$\displaystyle 100n + 7 = \Theta(n) $$

  • Proof: $100n + 7 \leq 107n$ for $n \geq 1$ → $O(n)$. $100n + 7 \geq 100n$ → $\Omega(n)$.

Recurrence Relations

Generating from Recursive Algorithms:

• Binary Search: $$\displaystyle T(n) = T(n/2) + \Theta(1) $$, with $$\displaystyle T(1) = \Theta(1) $$.

Solving Techniques:

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

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

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

   • Case 1: If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a}) $$.

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

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

Examples from Papers:

• $$\displaystyle T(n)=7T(n/2)+n^2 $$: Master Theorem, $$\displaystyle a=7, b=2, \log_b a \approx 2.81 $$. Since $$\displaystyle n^2 = O(n^{2.81 - \epsilon}) $$, Case 1 applies → $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81}) $$.

• $$\displaystyle T(n)=n+T(n/10)+T(7n/5) $$: This is not in standard Master form. Use recursion tree/substitution. The dominant cost comes from the larger subproblem $T(7n/5)$, leading to exponential growth ($$\displaystyle T(n) = \Omega((7/5)^n) $$).

Time Complexity Cases

[!TIP] Common Pitfall: Never state complexity as "Quicksort is $O(n \log n)$" without specifying it's the average-case. Worst-case is $$\displaystyle O(n^2) $$.

Lower Bound Theory

• Decision Trees: Used for comparison-based algorithms. Each internal node is a comparison, leaves are outcomes.

  • Selection Sort: For $n$ elements, there are $n!$ permutations. A binary decision tree must have at least $n!$ leaves. Height $$\displaystyle h \geq \log_2(n!) = \Omega(n \log n) $$. Thus, any comparison-based sorting algorithm has a worst-case lower bound of $\Omega(n \log n)$.

• Algebraic Lower Bounds: Based on the number of arithmetic operations inherently required (e.g., matrix multiplication requires at least $$\displaystyle n^2 $$ operations).

Stable Sorting Algorithms

Definition: A sorting algorithm is stable if it preserves the relative order of records with equal keys.

[!TIP] Exam Key: Stability matters when sorting by multiple keys (e.g., first by name, then by date). Use stable sorts to maintain the first sort order.

Trade-offs in Algorithm Design

• Readability vs. Optimization: Optimized code (e.g., bit manipulation, loop unrolling) can be harder to read/debug. Sacrifice readability only in performance-critical sections after profiling.

• Worst-case vs. Average-case: Choose worst-case for safety-critical systems (aviation, medical). Choose average-case for general applications where pathological inputs are improbable (e.g., Quicksort).

II. Divide and Conquer Paradigm

General Method and Control Abstraction

Steps:

1. Divide: Break the problem into smaller subproblems of the same type.

2. Conquer: Solve subproblems recursively. Base case: solve directly if small enough.

3. Combine: Merge subproblem solutions to form the original solution.

Control Abstraction:

DAC(P):

    if |P| is small then

        return Solve(P)

    else

        divide P into p1, p2, ..., pk

        for i = 1 to k

            yi = DAC(pi)

        return Combine(y1, y2, ..., yk)

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

Binary Search

• Algorithm: Search sorted array by repeatedly dividing the search interval in half.

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

• Solution: $$\displaystyle T(n) = \Theta(\log n) $$.

Merge Sort

• Algorithm:

  1. Divide array into two halves.

  2. Recursively sort each half.

  3. Merge two sorted halves (linear time).

• Complexity: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$ → $\Theta(n \log n)$ (Master Theorem Case 2).

• Stability: Yes (merge step preserves order).

• Trace Example: {23, 11, 5, 15, 68, 31, 4, 17}

  • Divide → {23,11,5,15} and {68,31,4,17}

  • Conquer → Sort each half recursively.

  • Combine → Merge {5,11,15,23} and {4,17,31,68} → {4,5,11,15,17,23,31,68}.

Quick Sort

• Algorithm:

  1. Partition: Choose a pivot, rearrange array so elements < pivot are left, > pivot are right.

  2. Recursively sort left and right partitions.

• Partition Schemes: Lomuto (simple), Hoare (more efficient, fewer swaps).

• Complexity:

  • Worst-case (pivot is min/max): $$\displaystyle T(n) = T(n-1) + \Theta(n) = \Theta(n^2) $$.

  • Average-case (pivot is median on average): $$\displaystyle T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n) $$.

• Trace Example: 65, 70, 75, 80, 85, 60, 55, 50 (using last element as pivot).

  • Pivot=50 → Partition: { } (left), {50} (pivot), {65,70,75,80,85,60,55} (right).

  • Recurse on right: Pivot=55 → { }, {55}, {65,70,75,80,85,60}.

  • Continue...

Strassen's Matrix Multiplication

• Algorithm (for 2x2):

  Given matrices $A, B$, compute 7 products:

  $$\displaystyle P_1 = (a_{11}+a_{22})(b_{11}+b_{22}) $$, $$\displaystyle P_2 = (a_{21}+a_{22})b_{11} $$, ..., $$\displaystyle P_7 = a_{11}(b_{12}-b_{22}) $$.

  Then compute result matrix $C$ from $$\displaystyle P_1...P_7 $$.

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

• Complexity: $$\displaystyle T(n) = O(n^{\log_2 7}) \approx O(n^{2.81}) $$ vs. Conventional $$\displaystyle O(n^3) $$.

• Example: Multiply $\begin{bmatrix}4 & 3\\2 & 1\end{bmatrix}$ and $\begin{bmatrix}2 & 5\\1 & 6\end{bmatrix}$.

  • $$\displaystyle P_1=(4+1)(2+6)=40 $$, $$\displaystyle P_2=(2+1)*2=6 $$, $$\displaystyle P_3=4*(5-6)=-4 $$, $$\displaystyle P_4=1*(6-2)=4 $$, $$\displaystyle P_5=(4-1)*6=18 $$, $$\displaystyle P_6=(4-5)*1=-1 $$, $$\displaystyle P_7=(4+3)*2=14 $$.

  • $$\displaystyle c_{11}=P_1+P_4-P_5+P_7=40+4-18+14=40 $$.

  • $$\displaystyle c_{12}=P_3+P_5=-4+18=14 $$.

  • $$\displaystyle c_{21}=P_2+P_4=6+4=10 $$.

  • $$\displaystyle c_{22}=P_1-P_2+P_3+P_6=40-6-4-1=29 $$.

  • Result: $\begin{bmatrix}40 & 14\\10 & 29\end{bmatrix}$.

Maximum and Minimum Elements

• Divide & Conquer: Split array, find min/max in each half, compare.

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

• Optimized Approach: Compare in pairs. For $n$ elements, requires at most $3\lfloor n/2 \rfloor$ comparisons (vs. $2n-2$ naive).

• Trace Example: 65, 70, 75, 80, 85, 60, 55, 50

  • Compare (65,70) → min=65, max=70.

  • Compare (75,80) → min=75, max=80.

  • Compare (85,60) → min=60, max=85.

  • Compare (55,50) → min=50, max=55.

  • Compare mins: (65,75,60,50) → overall min=50.

  • Compare maxs: (70,80,85,55) → overall max=85.

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 at each step.

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

• Both properties MUST be proven for a greedy algorithm to be correct.

Minimum Spanning Tree (MST)

Kruskal's Algorithm:

1. Sort all edges by weight (ascending).

2. Initialize forest (each vertex is a tree).

3. For each edge in sorted order: if it connects two different trees (no cycle), add it to MST (using Union-Find data structure for cycle detection).

• Complexity: $O(E \log E)$ or $O(E \log V)$.

• Correctness: Cut Property (lightest edge crossing any cut is in MST).

Prim's Algorithm:

1. Start with an arbitrary vertex.

2. Grow MST by adding the minimum-weight edge connecting the current MST to a vertex not yet in MST (using a priority queue).

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

• Uniqueness: With distinct edge weights, MST is unique.

[!TIP] Exam Distinction: Kruskal grows by edges (global sort), Prim grows by vertices (local min edge).

Job Sequencing with Deadlines

• Greedy Strategy: Sort jobs by decreasing profit. Schedule each job in the latest possible free slot before its deadline.

• Example: Profits (100, 10, 15, 27), Deadlines (2, 1, 2, 1).

  1. Sort by profit: Job1(100,d2), Job4(27,d1), Job3(15,d2), Job2(10,d1).

  2. Slot 2 (latest for Job1): Schedule Job1.

  3. Slot 1 (latest for Job4): Schedule Job4.

  4. Job3: no free slot ≤ d2.

  5. Job2: no free slot ≤ d1.

  • Optimal Profit = 100 + 27 = 127.

Fractional Knapsack

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

• Example: n=7, m=15, Profits (10,5,15,7,6,18,3), Weights (2,3,5,7,1,4,1).

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

  • Sorted: Item5(6,w1), Item1(5,w2), Item6(4.5,w4), Item7(3,w1), Item3(3,w5), Item2(1.67,w3), Item4(1,w7).

  • Take: Full Item5 (w=1, p=6), Full Item1 (w=2, p=10), Full Item6 (w=4, p=18), Full Item7 (w=1, p=3). Total w=8, p=37.

  • Remaining capacity=7. Next Item3 (w=5, p=15): take full, w=13, p=52.

  • Next Item2 (w=3, p=5): take fraction (2/3), p+=3.33, total p=55.33.

  • Optimal Profit ≈ 55.33.

Huffman Coding

• Construct Huffman Tree:

  1. Create leaf node for each symbol with its probability/frequency.

  2. While more than one node: remove two nodes with smallest probabilities, create a new internal node with them as children and probability = sum. Reinsert new node.

  3. Last node is root.

• Generate Codes: Assign 0 to left edge, 1 to right edge (or vice versa). Code for a symbol = path from root to leaf.

• Average Code Length: $$\displaystyle \sum_{i=1}^{n} p_i \cdot l_i $$, where $$\displaystyle l_i $$ is code length for symbol $i$.

• Example: Probabilities (0.07,0.09,0.12,0.22,0.23,0.27).

  1. Combine 0.07+0.09=0.16.

  2. Combine 0.12+0.16=0.28.

  3. Combine 0.22+0.23=0.45.

  4. Combine 0.27+0.28=0.55.

  5. Combine 0.45+0.55=1.0 (root).

  • Tree gives codes: e.g., f(0.27)=00, e(0.23)=01, d(0.22)=10, c(0.12)=110, b(0.09)=1110, a(0.07)=1111.

  • Average Length = $$\displaystyle 0.27*2 + 0.23*2 + 0.22*2 + 0.12*3 + 0.09*4 + 0.07*4 = 2.54 $$ bits/symbol.

Optimal Merge Patterns

• Problem: Merge $n$ sorted files of sizes $$\displaystyle s_1, s_2, ..., s_n $$ into one file. Cost to merge two files of size $a,b$ is $a+b$. Minimize total cost.

• Greedy Solution: Always merge the two smallest files first. Identical to Huffman coding (treat file sizes as frequencies).

• Example: File sizes {10, 20, 30, 40}.

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

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

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

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

IV. Dynamic Programming

Principle

• Overlapping Subproblems: Problem can be broken down into subproblems which are reused multiple times.

• Optimal Substructure: Optimal solution to problem can be constructed from optimal solutions to subproblems.

• Memoization (Top-down): Recursive solution with a table to store results of subproblems.

• Tabulation (Bottom-up): Fill a DP table iteratively, usually more efficient.

0/1 Knapsack Problem

• Problem: $n$ items, each with profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$. Knapsack capacity $W$. Maximize total profit without exceeding $W$. Each item is taken 0 or 1 time.

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

• Recurrence:

$$ dp[i][w] = \begin{cases} 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} $$

• Example: Profits (11,21,31,33), Weights (2,12,23,15), $$\displaystyle W=42 $$, $$\displaystyle n=4 $$.

  • Build 5x43 table. Final answer $$\displaystyle dp[4][42] = 62 $$ (items 1,3,4: 11+31+33=75? Wait, check weights: 2+23+15=40 ≤42, profit=11+31+33=75. But 62? Let's recalc properly).

  • Correct Solution: Optimal is items 2 and 4? Weight 12+15=27, profit 21+33=54. Items 1,3,4: weight 2+23+15=40, profit 11+31+33=75. Items 3 alone: 31. Max profit is 75. (The example in blueprint might have different numbers; always compute fresh).

Floyd-Warshall Algorithm

• Problem: All-pairs shortest paths in a weighted graph (no negative cycles).

• Algorithm: $n \times n$ DP table dist. Initialize dist[i][j] = weight of edge (i,j) or ∞ if no edge, 0 if i=j.

  For k from 1 to n:

  For i from 1 to n:
  
      For j from 1 to n:
  
          `dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])`
  

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

• Output: dist[i][j] contains shortest path distance from i to j. Can also compute predecessor matrix to reconstruct paths.

Multistage Graph

• Problem: Find shortest path from source (stage 1) to sink (stage k) in a directed acyclic graph (DAG) where vertices are partitioned into stages.

• DP Approach (Backward):

  • Let $$\displaystyle f(v_i) $$ = cost of shortest path from vertex $$\displaystyle v_i $$ to sink.

  • $$\displaystyle f(\text{sink}) = 0 $$.

  • For vertices in reverse stage order: $$\displaystyle f(v_i) = \min_{(v_i,v_j) \in E} \{ c(v_i,v_j) + f(v_j) \} $$.

• Algorithm: Compute $f(v)$ for all vertices in topological order (reverse). Cost of optimal path = $f(\text{source})$.

• Computing Time: $O(|V|+|E|)$ if graph is stored appropriately (each vertex has out-degree to next stage only).

Reliability Design

• Problem: Maximize reliability of a series-parallel system under a cost constraint.

  • Series: Reliability $$\displaystyle R_{series} = \prod R_i $$.

  • Parallel: Reliability $$\displaystyle R_{parallel} = 1 - \prod (1-R_i) $$.

• DP Approach: For each stage $i$, consider all possible device types $j$ with cost $$\displaystyle c_{ij} $$ and reliability $$\displaystyle r_{ij} $$. Let $R[i][b]$ = max reliability for first $i$ stages with budget $b$.

• Recurrence: $$\displaystyle R[i][b] = \max_{j} \{ r_{ij} \cdot R[i-1][b - c_{ij}] \} $$ (for series connection).

• Example: 3 stages, costs (30,15,20), reliabilities (0.9,0.8,0.5), budget $105.

  • Stage 1: Only device type D1 (cost30, r=0.9).

  • Stage 2: D1 (cost30, r=0.8) or D2 (cost15, r=0.8)? Assume one device type per stage. Budget allocation: try combinations.

  • Optimal: Use D1 for all stages? Cost=90, Reliability=0.90.80.5=0.36. With leftover $15, can we upgrade? If stage 2 has a better device? Need specific device options per stage. Typically, DP table over stages and budget.

V. Backtracking and Branch and Bound

Backtracking

• Concept: Systematic way to traverse the state-space tree of all possible solutions. Build solutions incrementally, prune (backtrack) when a partial solution cannot be extended to a valid/optimal solution.

• General Algorithm:

  
      if candidate is a complete solution then
  
          output candidate
  
          return
  
      for each possible extension of candidate do
  
          if extension is feasible then
  
              backtrack(extension)
  
  

• State-Space Tree: Nodes represent partial solutions. Edges represent choices. Leaves are complete solutions or dead ends.

n-Queens Problem

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

• Backtracking: Place queens row by row. For each row, try each column. Check if placement is safe (no conflict with previously placed queens in columns or diagonals).

• 4-Queens Solution: (2,4,1,3) meaning queen in row1 col2, row2 col4, row3 col1, row4 col3.

• State-Space Tree: Root → 4 choices for row1 → for each, up to 4 for row2 (pruned if conflict) → etc.

Subset Sum Problem

• Problem: Given set $$\displaystyle S = \{s_1, s_2, ..., s_n\} $$ and target $X$, find a subset whose sum is exactly $X$.

• Backtracking: Consider elements one by one. At each step, branch: include current element (reduce target) or exclude it. Prune if current sum > X or if sum of remaining elements + current sum < X.

• Example: $$\displaystyle S=\{1,3,4,5\}, X=8 $$.

  • Start with empty set, sum=0, index=1.

  • Include 1 → sum=1, index=2.

    • Include 3 → sum=4, index=3.

      • Include 4 → sum=8 → Solution {1,3,4}.

      • Exclude 4 → sum=4, index=4 → Include 5 → sum=9>8 (prune).

    • Exclude 3 → sum=1, index=3...

  • Exclude 1 → sum=0, index=2...

Hamiltonian Cycle

• Problem: Find a cycle in an undirected graph that visits each vertex exactly once and returns to start.

• Backtracking: Start at a vertex. Build path vertex by vertex. At each step, choose an adjacent vertex not yet in path. If path length = n and last vertex connects to start, solution found. Prune if no unvisited adjacent vertices.

• Example Graph: Often a small graph (4-5 vertices) provided in exam.

Graph Coloring (m-coloring)

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

• Backtracking: Assign colors to vertices one by one (in some order). For each vertex, try colors 1..m. Check if color is safe (no neighbor has same color). Backtrack if no color possible.

• Example: Color a given graph with $$\displaystyle m=3 $$.

Branch and Bound

• Concept: Similar to backtracking but uses bounding functions to compute a lower/upper bound on the best possible solution in a subtree. If bound is worse than current best, prune entire subtree (no backtracking into it). Often uses a priority queue (best-first search).

• Traveling Salesman Problem (TSP):

  • Reduction Method: For each edge $(i,j)$, temporarily set cost $$\displaystyle c_{ij} = \infty $$. Compute a lower bound on tour cost for the reduced matrix:

    1. Reduce each row (subtract min of row).

    2. Reduce each column (subtract min of column).

    3. Sum all row/column minima = bound.

  • Nearest Neighbor Approximation (for initial solution): Start at a city, repeatedly go to nearest unvisited city. Return to start. Gives a feasible tour, not necessarily optimal.

  • Accuracy Ratio: $$\displaystyle \frac{\text{Cost of B\&B solution}}{\text{Cost of optimal solution}} $$ (or vice versa). For approximation algorithms, ratio $\leq$ some constant.

  • Example Matrix (5x5): Provided in Dec 2024 paper. Apply reduction method at each node of state-space tree (partial tours).

VI. Graph Algorithms

BFS vs DFS

Topological Sorting

• For DAGs only. Linear ordering of vertices such that for every directed edge $(u,v)$, $u$ comes before $v$.

• Using DFS: Perform DFS, output vertices in reverse postorder (when finishing a vertex, push to stack).

• Example: Given a DAG (common in papers), apply DFS from an arbitrary start, list vertices in finishing order, reverse to get topological sort.

Single Source Shortest Path

• Dijkstra's Algorithm:

  • Requirements: Non-negative edge weights.

  • Greedy: Maintain set $S$ of vertices with finalized shortest paths. Repeatedly select vertex $u \notin S$ with minimum tentative distance, relax its outgoing edges.

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

• Bellman-Ford Algorithm:

  • Requirements: Can handle negative weights (but no negative cycles).

  • DP: Relax all edges $V-1$ times. On $V$-th iteration, check for negative cycles.

  • Complexity: $O(VE)$.

• Example Application: Given a graph (common in Jun 2024, Dec 2024 papers), apply step-by-step from a source vertex.

VII. Tree Data Structures

Binary Search Tree (BST)

• Property: For any node, all keys in left subtree < node's key, all keys in right subtree > node's key.

• Operations:

  • Search: $O(h)$ average, $O(n)$ worst (skewed).

  • Insert: Search for null leaf, insert there.

  • Delete:

    1. Leaf: Simply remove.

    2. One child: Replace node with its child.

    3. Two children: Find inorder successor (smallest in right subtree) or predecessor (largest in left subtree). Copy its key to node, then delete successor/predecessor (which has at most one child).

• Example Sequence: 20,49,41,93,69,90,76,62,81,75,10,79,87,38. Build BST step-by-step.

• Delete 41 and 76: Show tree after each deletion.

Binary Heaps and Heap Sort

• Binary Heap: Complete binary tree satisfying heap property.

  • Max-Heap: Parent ≥ children.

  • Min-Heap: Parent ≤ children.

• Array Representation: Root at index 1. Parent(i)=⌊i/2⌋, Left(i)=2i, Right(i)=2i+1.

• Heapify: Restore heap property downward from a node (O(log n)).

• Build-Heap: Convert an array into a heap by calling heapify on all non-leaf nodes bottom-up (O(n)).

• Heap Sort:

  1. Build max-heap from array.

  2. Swap root (max) with last element, reduce heap size by 1.

  3. Heapify new root.

  4. Repeat.

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

• Stability: Unstable (swaps can change relative order of equal keys).

AVL Trees

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

• Rotations (for rebalancing after insertion/deletion):

  • LL (Right Rotation): BF(node)=+2, BF(left-child)=+1.

  • RR (Left Rotation): BF(node)=-2, BF(right-child)=-1.

  • LR (Left-Right): BF(node)=+2, BF(left-child)=-1 → Left-rotate left-child, then right-rotate node.

  • RL (Right-Left): BF(node)=-2, BF(right-child)=+1 → Right-rotate right-child, then left-rotate node.

• Insertion: Insert as in BST, then update heights and rebalance up the path.

• Deletion: More complex; may require multiple rotations.

B-Trees

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

• Properties: All leaves at same level. Height is $$\displaystyle O(\log_m n) $$.

• Insertion:

  1. Find leaf node where key should go.

  2. Insert key in sorted order.

  3. If node overflows (has $m$ keys), split it: median key moves up to parent, left/right halves become children.

• Deletion Cases:

  1. From leaf: Remove key. If underflow (keys < min), borrow from sibling or merge with sibling.

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

• Example: Given a B-tree (order 5) and a sequence of insertions/deletions, show step-by-step (common in Jun 2022, Jun 2024).

Binomial Heaps

• Structure: Collection of binomial trees (like B-trees but different). A binomial tree of order $k$ has $$\displaystyle 2^k $$ nodes, height $k$, root has degree $k$, children are roots of binomial trees of orders $k-1, k-2, ..., 0$.

• Properties: Heap-ordered (min-heap or max-heap). At most one binomial tree of any order (like binary representation of number of nodes).

• Union (Merging):

  1. Merge two root lists (sorted by order) like merging two sorted lists.

  2. Scan merged list: if two consecutive trees have same order, link them (make one root child of the other) to maintain at most one per order.

• Find-Min: Scan roots (O(log n)).

• Example: Unite two binomial heaps (given as lists of trees with orders and keys).

2-3 Trees

• Structure: Every internal node has 2 or 3 children.

  • 2-node: 1 key, 2 children.

  • 3-node: 2 keys (sorted), 3 children.

• All leaves at same level.

• Operations:

  • Search: Compare with keys in node to decide child.

  • Insert: Insert in leaf. If leaf becomes a 4-node (3 keys), split it: middle key moves up to parent, left/right become 2-nodes.

• Comparison with B-Trees: 2-3 tree is a B-tree of order 3 (m=3). B-trees generalize to higher orders.

Binary Tree Traversals and Construction

• Traversals:

  • Inorder (LNR): Left, Node, Right → Gives sorted order for BST.

  • Preorder (NLR): Node, Left, Right → Useful for copying tree structure.

  • Postorder (LRN): Left, Right, Node → Useful for deletion.

• Constructing from Traversals:

  • Inorder + Preorder: First element of preorder is root. Find root in inorder → left subtree (inorder left part), right subtree (inorder right part). Recurse.

  • Example: Inorder: B C A E G D H F I J, Preorder: A B C D E G F H I J.

    1. Root = A (from preorder).

    2. In inorder: left=B C A? Wait, root A is at position 3. Left subtree inorder=B C, right subtree inorder=E G D H F I J.

    3. Preorder after A: B C D E G F H I J. Left subtree preorder = first 2 elements B C (matches size of left inorder). Right subtree preorder = D E G F H I J.

    4. Recurse on left: Root=B, left inorder= , right inorder=C → B has right child C.

    5. Recurse on right: Root=D, left inorder=E G, right inorder=H F I J... Continue.

  • Postorder: After constructing tree, traverse in postorder: C B G E H I J F D A? Let's compute properly from constructed tree.

VIII. Complexity Theory

Complexity Classes

Relationships

P ⊆ NP

NP-complete ⊆ NP-hard

NP-complete = NP ∩ NP-hard

Diagram: Three concentric circles: Smallest P inside NP. NP-complete at intersection of NP and NP-hard. NP-hard outside NP (includes problems not in NP).

Reductions

• Polynomial-time Reduction: Transform instance of problem $A$ to instance of problem $B$ in polynomial time. If $B$ has a polynomial solution, so does $A$.

• To prove NP-completeness:

  1. Show problem is in NP (certificate verifiable in poly-time).

  2. Reduce a known NP-complete problem to it.

• Example: SAT to 3-SAT: Transform any clause with $$\displaystyle k>3 $$ literals into a set of 3-literal clauses using new variables.

Approximation Algorithms

• For NP-hard optimization problems where exact solution is infeasible.

• Approximation Ratio $\rho$: For minimization, $$\displaystyle \frac{\text{Approx Cost}}{\text{Opt Cost}} \leq \rho $$. For maximization, $$\displaystyle \frac{\text{Opt Cost}}{\text{Approx Cost}} \leq \rho $$.

• Examples:

  • TSP Nearest Neighbor: Heuristic, no constant bound on ratio for general metric TSP.

  • Fractional Knapsack: Greedy is optimal (ratio=1). 0/1 Knapsack has PTAS.

  • Vertex Cover: Simple 2-approximation.

IX. Special Topics and Emerging Areas

Data Stream Algorithms

• Context: Process massive data streams (e.g., network packets, sensor data) where storing all data is impossible.

• Goal: Compute summaries (synopses) with small memory footprint.

• Examples:

  • Count-Distinct: Estimate number of distinct elements (e.g., Flajolet-Martin algorithm).

  • Moments: Estimate frequency moments (e.g., $$\displaystyle F_0, F_1, F_2 $$).

Logic Optimization

• Context: Minimize Boolean expressions in digital circuit design.

• Goal: Reduce number of gates/literals while preserving functionality.

• Techniques: Karnaugh maps, Quine-McCluskey algorithm, Espresso heuristic.

Data Transfer Optimization

• Context: Minimize data movement cost in networks, parallel systems, or I/O.

• Goal: Schedule data transfers to minimize total communication time or bandwidth usage.

• Techniques: Often modeled as graph problems (minimum spanning tree for broadcasting, flow networks).

Parallel Algorithms

• Design Paradigms: Divide & Conquer (parallel recursion), Greedy (parallel priority queues).

• Complexity Measures:

  • Work ($$\displaystyle T_1 $$): Total operations across all processors.

  • Span ($$\displaystyle T_\infty $$): Longest path of dependencies (critical path).

  • Parallel Time on $p$ processors: $$\displaystyle T_p \geq \max(T_\infty, T_1/p) $$.

• PRAM Model: Parallel Random Access Machine (shared memory, synchronous). Variants: CRCW, CREW, EREW.

END OF UNIT 1 NOTES