Analysis & Design of Algorithms (AL-402) Unit 4 Notes

UNIT 4: Analysis & Design of Algorithms

I. Fundamentals of Algorithm Analysis

Asymptotic Notations

Used to describe the limiting behavior of a function, focusing on growth rates as input size n → ∞. Ignore constant factors and lower-order terms.

Notation	Meaning	Formal Definition	Example
Big O (O)	Upper bound (worst-case)	$$\displaystyle f(n) = O(g(n)) $$ if ∃ $$\displaystyle c > 0 $$, $$\displaystyle n_0 $$ such that $0 \le f(n) \le c \cdot g(n)$ ∀ $$\displaystyle n \ge n_0 $$	$$\displaystyle 3n^2 + 2n + 1 = O(n^2) $$
Omega (Ω)	Lower bound (best-case)	$$\displaystyle f(n) = \Omega(g(n)) $$ if ∃ $$\displaystyle c > 0 $$, $$\displaystyle n_0 $$ such that $0 \le c \cdot g(n) \le f(n)$ ∀ $$\displaystyle n \ge n_0 $$	$$\displaystyle 3n^2 + 2n + 1 = \Omega(n^2) $$
Theta (Θ)	Tight bound (average-case often)	$$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$	$$\displaystyle 3n^2 + 2n + 1 = \Theta(n^2) $$

[!TIP] Exam Tip: For polynomial $$\displaystyle a_k n^k + ... + a_0 $$, $$\displaystyle \Theta(n^k) $$. For loops, multiply inner/outer complexities. Recursions use recurrence trees or Master Theorem.

Recurrence Relations

Define $T(n)$ in terms of smaller inputs.

1. Substitution Method

Guess a bound, then prove by induction.
Example (Quicksort average): $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) $$. Guess $$\displaystyle T(n) = O(n \log n) $$, substitute and verify.

2. Master Theorem

For $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $a \ge 1$, $$\displaystyle b > 1 $$, $f(n)$ asymptotically positive:

Case 1: If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$ for $$\displaystyle \epsilon > 0 $$, 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) \le cf(n)$ for $$\displaystyle c < 1 $$, then $$\displaystyle T(n) = \Theta(f(n)) $$.

[!EXAMPLE] Solve: $$\displaystyle T(n)=7T(n/2)+2n^2 $$

$$\displaystyle a=7, b=2, \log_b a = \log_2 7 \approx 2.807 $$, $$\displaystyle f(n)=2n^2 $$. Since $$\displaystyle n^2 = O(n^{\log_2 7 - \epsilon}) $$ for $\epsilon \approx 0.807$, Case 1 applies.

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

Divide and Conquer Analysis

Merge Sort

Algorithm: Divide array into halves, recursively sort, merge two sorted halves.
Complexity: Recurrence $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$. By Master Theorem Case 2 ($$\displaystyle f(n)=\Theta(n^{\log_2 2}) $$), $$\displaystyle T(n) = \Theta(n \log n) $$.

Strassen’s Matrix Multiplication

Algorithm: For two $n \times n$ matrices (assume $n$ is power of 2), compute 7 products recursively instead of 8.
1. Divide each matrix into 4 submatrices.
2. Compute 7 matrices $$\displaystyle M_1 $$ to $$\displaystyle M_7 $$ using combinations.
3. Combine to get result submatrices.
Complexity: Recurrence $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$. By Master Theorem Case 1 ($$\displaystyle \log_2 7 \approx 2.807 > 2 $$), $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81}) $$.

\boxed{\text{Time: } O(n^{2.81}) \text{ vs. naive } O(n^3)}

Quicksort Average Case

Recurrence: $$\displaystyle T(n) = \frac{1}{n} \sum_{k=0}^{n-1} [T(k) + T(n-k-1)] + \Theta(n) $$.
Solution: Assume $T(n) \le c n \log n$. Substitute and show holds for appropriate $c$. Average case is $\boxed{O(n \log n)}$.

II. Greedy Algorithms

Greedy Choice Property & Optimal Substructure

Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum without reconsidering past choices.
Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems.
Proof of Correctness: Must prove both properties. Show greedy choice is safe (leads to optimal solution) and that remaining subproblem is optimally solved recursively.

Job Sequencing with Deadlines

Problem: Maximize profit for $n$ jobs, each with profit $$\displaystyle P_i $$, deadline $$\displaystyle d_i $$ (1 unit time per job). Schedule at most one job per time slot.
Algorithm (Greedy by Profit):
1. Sort jobs descending by profit.
2. Initialize array slot[1..max_deadline] = false.
3. For each job in sorted order, find latest free slot ≤ its deadline. If found, schedule job.
Example: $$\displaystyle n=4 $$, $$\displaystyle P=(100,10,15,27) $$, $$\displaystyle d=(2,1,2,1) $$.
- Sorted: Job1(100,d2), Job4(27,d1), Job3(15,d2), Job2(10,d1).
- Schedule: Job1 at t=2, Job4 at t=1. Jobs 2,3 rejected.
- Optimal Profit = 127.

Fractional Knapsack

Problem: Fill knapsack of capacity $W$ with items having profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$. Items can be taken fractionally.
Algorithm: Compute ratio $$\displaystyle r_i = p_i/w_i $$. Sort by descending $$\displaystyle r_i $$. Take items in order until full; last item may be fractional.
Example: $$\displaystyle n=7, m=15 $$, $$\displaystyle p=(10,5,15,7,6,18,3) $$, $$\displaystyle w=(2,3,5,7,1,4,1) $$.
- Ratios: (5, 1.67, 3, 1, 6, 4.5, 3). Sorted: Item1(5), Item6(4.5), Item5(6), Item3(3), Item7(3), Item2(1.67), Item4(1).
- Take full: Item1(2), Item6(4), Item5(1) → total weight 7. Remaining 8.
- Next Item3 (w=5): take full → weight 12.
- Next Item7 (w=1): take full → weight 13.
- Next Item2 (w=3): take 2/3 → weight 15.
- Profit = $$\displaystyle 10 + 18 + 6 + 15 + 3 + (5 \times 2/3) = 52 + 3.33 = 55.33 $$.

Huffman Coding

Algorithm (Tree Construction):
1. Create min-heap of nodes (character, frequency).
2. While heap size > 1:
  - Extract two min-frequency nodes $x,y$.
  - Create new node with freq = $x.freq + y.freq$, left=$x$, right=$y$.
  - Insert new node into heap.
3. Remaining node is root.
Example: Chars: a(5), b(9), c(12), d(13), e(16), f(45). Build tree; codes: f(0), c(101), d(110), a(1000), b(1001), e(11).

Optimal Merge Pattern

Problem: Merge $n$ sorted files of sizes $$\displaystyle s_1,...,s_n $$ into one file with minimal total merge cost (cost = sum of sizes merged).
Algorithm: Same as Huffman—use min-heap, repeatedly merge two smallest files.
Example: Files: 10, 20, 30, 40, 50, 60.
- Merge 10+20=30 (cost 30), list: 30,30,40,50,60.
- Merge 30+30=60 (cost 60), list: 40,50,60,60.
- Merge 40+50=90 (cost 90), list: 60,60,90.
- Merge 60+60=120 (cost 120), list: 90,120.
- Merge 90+120=210 (cost 210).
- Total Cost = 30+60+90+120+210 = 510.

Single Source Shortest Path: Dijkstra’s Algorithm

Problem: Find shortest paths from source vertex $s$ to all vertices in a graph with non-negative edge weights.
Algorithm:
1. Initialize dist[v] = ∞ for all $v$, dist[s]=0. Set S = {} (finalized vertices).
2. While not all vertices in S:
  - Pick vertex $u \notin S$ with minimum dist[u].
  - Add $u$ to S.
  - For each neighbor $v$ of $u$, if dist[u] + w(u,v) < dist[v], update dist[v].
Complexity: $$\displaystyle O(V^2) $$ with array; $O(E \log V)$ with min-heap (priority queue).
Example: Apply to given graph (standard step-by-step relaxation).

Minimum Spanning Tree: Kruskal’s Algorithm

Problem: Find spanning tree with minimum total edge weight in an undirected graph.
Algorithm:
1. Sort all edges by ascending weight.
2. Initialize forest $F$ = each vertex as separate tree.
3. For each edge $(u,v)$ in sorted order:
  - If $u$ and $v$ are in different trees (find using Union-Find), add edge to $F$ and union the trees.
Complexity: Sorting $O(E \log E)$; Union-Find operations nearly $O(E \alpha(V))$ → overall $O(E \log E)$.
Example: Apply to given graph, pick edges in order, skip if cycle formed.

III. Dynamic Programming

Multistage Graph Problem

Problem: Find shortest path from start vertex $s$ to terminal vertex $t$ in a directed acyclic graph (DAG) with stages.
Forward Approach:
- Let $C(i)$ = cost from vertex $i$ to $t$.
- $$\displaystyle C(t)=0 $$. For stage $k$ from last to first: $$\displaystyle C(i) = \min_{j \in \text{successors}(i)} [c(i,j) + C(j)] $$.
Backward Approach: Compute $F(i)$ = cost from $s$ to $i$; $$\displaystyle F(s)=0 $$; $$\displaystyle F(j) = \min_{i \in \text{predecessors}(j)} [F(i) + c(i,j)] $$.

Algorithm (Forward):


cost[t] = 0

for k = n-1 downto 1:

  for each vertex i in stage k:

    cost[i] = min{ c(i,j) + cost[j] for j in stage k+1 }

    next[i] = argmin

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

Reliability Design Problem

Problem: Design a system with $n$ stages in series. Each stage $i$ can have $$\displaystyle m_i $$ parallel devices of type $i$ (cost $$\displaystyle c_i $$, reliability $$\displaystyle r_i $$). Maximize overall reliability $$\displaystyle R = \prod_{i=1}^n (1 - (1-r_i)^{m_i}) $$ subject to total cost ≤ $B$.
Dynamic Programming:
- Let $R[i][b]$ = max reliability for first $i$ stages with budget $b$.
- Recurrence: $$\displaystyle R[i][b] = \max_{0 \le x \le \lfloor b/c_i \rfloor} \{ (1 - (1-r_i)^x) \cdot R[i-1][b - x \cdot c_i] \} $$.
- Base: $$\displaystyle R[0][b]=1 $$ for all $b$.
Example: 3 stages, costs (30,15,20), reliabilities (0.9,0.8,0.5), budget $105$. Compute table.

Floyd-Warshall Algorithm (All-Pairs Shortest Paths)

Problem: Find shortest distances between every pair of vertices in a weighted graph (negative edges allowed, no negative cycles).

Algorithm:


let dist be a |V| x |V| array

initialize dist[i][j] = weight(i,j) if edge exists, else ∞; dist[i][i]=0

for k = 1 to |V|:

  for i = 1 to |V|:

    for j = 1 to |V|:

      if dist[i][j] > dist[i][k] + dist[k][j]:

        dist[i][j] = dist[i][k] + dist[k][j]

Complexity: $$\displaystyle O(V^3) $$.
Example: Apply to given graph; update matrix step-by-step for $$\displaystyle k=1,2,3,4,5 $$.

IV. Backtracking

n-Queens Problem

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

Algorithm (Backtracking):


placeQueens(row):

  if row == n: solution found, print

  else:

    for col = 0 to n-1:

      if isSafe(row, col):

        place queen at (row,col)

        placeQueens(row+1)

        remove queen (backtrack)

isSafe(row,col): check no queen in same column above, and diagonals (upper-left, upper-right).

Example (4-Queen): Solutions: [2,4,1,3] and [3,1,4,2] (1-indexed columns per row).
Example (8-Queen): 92 distinct solutions.

Graph Coloring (m-coloring)

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

Algorithm:


colorGraph(v):

  if v == n: solution found

  else:

    for c = 1 to m:

      if no neighbor of v has color c:

        assign color c to v

        colorGraph(v+1)

        remove color (backtrack)

Example: For given graph and $$\displaystyle m=3 $$, try assignments recursively.

Hamiltonian Cycle

Problem: Find a cycle that visits each vertex exactly once and returns to start.

Algorithm:


Hamiltonian(v, count):

  if count == n and edge(v, start) exists: solution found

  else:

    for each neighbor u of v:

      if u not in path:

        path[count] = u

        Hamiltonian(u, count+1)

        remove u from path (backtrack)

Example: For given graph, start from vertex 0, explore all permutations.

V. Branch and Bound

Travelling Salesperson Problem (TSP)

Problem: Find minimum cost Hamiltonian cycle in a complete weighted graph.

1. Reduction Method (Row/Column Subtraction)

Step 1: For each row, subtract min element of that row from all elements in row.
Step 2: For each column, subtract min element of that column from all elements in column.
Step 3: The sum of all subtracted minima is a lower bound for any tour starting from that node.

2. Branch and Bound Approach

State: Partial path (e.g., 1→2→3), current cost, reduced cost matrix.
Bounding Function: Cost so far + minimum possible additional cost (from reduced matrix: sum of min uncovered row/col, plus 0 if edge in path).
Search Tree: Nodes represent partial tours. Use priority queue (min-heap) ordered by bound. Expand node with smallest bound.
Example (Dec 2024 matrix):

$$ \begin{bmatrix} \infty & 20 & 30 & 10 & 11 \\ 15 & \infty & 16 & 4 & 2 \\ 3 & 5 & \infty & 2 & 4 \\ 19 & 6 & 18 & \infty & 3 \\ 16 & 4 & 7 & 16 & \infty \end{bmatrix} $$

Start from node 1: reduce matrix, compute bound.
Branch to 2,3,4,5; compute bounds for each child.
Expand node with smallest bound, continue until complete tour found and all nodes with bound ≥ best cost are pruned.

VI. Complexity Theory

Complexity Classes

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

\boxed{P = { L \mid \exists \text{ poly-time deterministic TM that decides } L }}
NP: Problems verifiable in polynomial time (or solvable by non-deterministic TM in poly-time).

\boxed{NP = { L \mid \exists \text{ poly-time verifier } V \text{ s.t. } x \in L \Leftrightarrow \exists y, V(x,y)=\text{accept} }}
NP-Hard: Problems at least as hard as hardest in NP. Every problem in NP reduces to it (not necessarily in NP).
NP-Complete: Problems in NP that are NP-Hard.

\boxed{NP\text{-}Complete = NP \cap NP\text{-}Hard}

Relationships

Venn Diagram: P ⊆ NP. NP-Complete ⊆ NP. NP-Hard may contain NP-Complete and harder problems (e.g., Halting Problem).
Key: If any NP-Complete problem has poly-time solution, then P = NP.

Reductions

Polynomial-time Reduction: Transform instance of problem $A$ to instance of problem $B$ in poly-time, such that answer is “yes” for $A$ iff “yes” for $B$.
Purpose: Show $B$ is at least as hard as $A$. To prove $B$ is NP-Hard, reduce known NP-Complete problem to $B$.

VII. Advanced Data Structures

B-trees

Order $m$: Each internal node (except root) has $\lceil m/2 \rceil$ to $m$ children. Root has at least 2 children if not leaf.
Height $h$: For $n$ keys, $$\displaystyle h \le \log_{\lceil m/2 \rceil} \left( \frac{n+1}{2} \right) $$.
Properties: All leaves at same level. Keys in node sorted. Search in $$\displaystyle O(h) = O(\log n) $$.
Insertion:
1. Search leaf where key should go.
2. Insert key in sorted order.
3. If leaf overflows ($$\displaystyle > m-1 $$ keys), split:
  - Median moves up to parent.
  - Left half stays, right half becomes new node.
4. Propagate split up if parent overflows.
Example: Insert into B-tree of order 5 (max 4 keys/node). Show step-by-step splits.

VIII. Specialized Algorithm Topics

Data Stream Algorithms

Model: Data arrives as stream, cannot store entirely. One pass, limited memory.
Techniques:
- Sampling: Reservoir sampling for uniform random sample.
- Sketching: Count-Min Sketch for frequency estimation.
- Heavy Hitters: Misra-Gries algorithm (find items > ε fraction).
Goal: Approximate queries (frequency, quantiles, distinct counts) with sublinear memory.

Approximation Algorithms

Purpose: For NP-Hard problems, find solution in poly-time with guarantee on closeness to optimum.
Performance Ratio $\rho$: For minimization, $\text{cost}(A) \le \rho \cdot \text{OPT}$. For maximization, $\text{profit}(A) \ge \text{OPT}/\rho$.
Example: Vertex Cover 2-approximation, TSP triangle inequality 2-approximation.

Data Transfer Optimization

Problem: Transfer data from sources to sinks with capacities, minimize total transfer cost or time.
Approach: Model as network flow (max flow, min cost flow) or bipartite matching (Hungarian algorithm for assignment).
Key: Often solved by linear programming or combinatorial algorithms.

Parallel Algorithms

Design Issues: Decomposition (task/data), load balancing, synchronization, communication overhead.
Complexity Measures:
- Work $W$: Total operations across all processors.
- Span $S$: Longest path in dependency graph (critical path).
- Speedup $$\displaystyle S_p = T_1 / T_p $$ (ideal linear: $$\displaystyle S_p = p $$).
- Efficiency $$\displaystyle E_p = S_p / p $$.
- Parallelism $$\displaystyle = W/S $$ (max possible speedup).
PRAM Model: Shared memory, synchronous steps. Variants: CRCW, CREW, EREW.

Logic Optimization

Boolean Functions: Minimize cost (gate count, delay) of implementing Boolean expression.
Techniques:
- Karnaugh Map (K-map): Visual grouping for up to 4 variables.
- Quine-McCluskey: Tabular method for many variables (prime implicants, essential primes, covering).
- Espresso: Heuristic for large functions.
Goal: Find minimal sum-of-products or product-of-sums.

END OF UNIT 4 NOTES

Account

Analysis & Design of Algorithms (AL-402) - Unit 4 Short Notes

UNIT 4: Analysis & Design of Algorithms

I. Fundamentals of Algorithm Analysis

Asymptotic Notations

Recurrence Relations

Divide and Conquer Analysis

II. Greedy Algorithms

Greedy Choice Property & Optimal Substructure

Job Sequencing with Deadlines

Fractional Knapsack

Huffman Coding

Optimal Merge Pattern

Single Source Shortest Path: Dijkstra’s Algorithm

Minimum Spanning Tree: Kruskal’s Algorithm

III. Dynamic Programming

Multistage Graph Problem

Reliability Design Problem

Floyd-Warshall Algorithm (All-Pairs Shortest Paths)

IV. Backtracking

n-Queens Problem

Graph Coloring (m-coloring)

Hamiltonian Cycle

V. Branch and Bound

Travelling Salesperson Problem (TSP)

VI. Complexity Theory

Complexity Classes

Relationships

Reductions

VII. Advanced Data Structures

B-trees

VIII. Specialized Algorithm Topics

Data Stream Algorithms

Approximation Algorithms

Data Transfer Optimization

Parallel Algorithms

Logic Optimization