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

UNIT 1: Analysis & Design of Algorithms

I. Fundamentals of Algorithm Analysis

Asymptotic Notations

Used to describe the limiting behavior of a function, representing algorithm efficiency as input size grows.

[!TIP] Exam Focus: Be prepared to prove a function belongs to a notation class using the formal definition.

Recurrence Relations

Equations defining a sequence where each term is a function of its predecessors. Common for divide-and-conquer algorithms.

1. Substitution Method

• Guess the form of the solution.

• Prove it by mathematical induction.

• Example (Dec 2024): Solve $$\displaystyle T(n)=7T\left(\frac{n}{2}\right)+2n^2 $$.

  • Guess: $$\displaystyle T(n) = O(n^{\log_2 7}) \approx O(n^{2.81}) $$.

  • Verify by induction: Assume $$\displaystyle T(k) \leq c \cdot k^{\log_2 7} $$ for $$\displaystyle k < n $$.

  • $$\displaystyle T(n) = 7c\left(\frac{n}{2}\right)^{\log_2 7} + 2n^2 = cn^{\log_2 7} + 2n^2 $$.

  • For $c \geq 3$, $$\displaystyle cn^{\log_2 7} + 2n^2 \leq cn^{\log_2 7} $$ for sufficiently large $n$.

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

2. Master Theorem

For recurrences of the form: $$\displaystyle T(n) = aT\left(\frac{n}{b}\right) + f(n) $$, where $$\displaystyle a \geq 1, b > 1 $$.

Let $$\displaystyle c = \log_b a $$. Compare $f(n)$ with $$\displaystyle n^c $$:

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

• Case 2: If $$\displaystyle f(n) = \Theta(n^c \log^k n) $$, then $$\displaystyle T(n) = \Theta(n^c \log^{k+1} n) $$.

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

[!CAUTION] Common Pitfall: Ensure regularity condition ($af(n/b) \leq kf(n)$) holds for Case 3.

Case Analysis: Quicksort Example

• Best Case: Pivot always divides array into nearly equal halves.

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

• Average Case: Pivot is equally likely to be any element.

  • Expected number of comparisons: $\approx 1.39 n \log n$.

  • $$\displaystyle \boxed{\text{Average Case Time} = \Theta(n \log n)} $$ (Proved via recurrence or probability).

• Worst Case: Pivot is smallest or largest element (already sorted input).

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

II. Divide and Conquer Paradigm

Merge Sort

Algorithm:

1. Divide: Split array into two halves.

2. Conquer: Recursively sort each half.

3. Combine: Merge two sorted halves.

Pseudocode:

MERGE-SORT(A, p, r)

  if p < r

    q = ⌊(p+r)/2⌋

    MERGE-SORT(A, p, q)

    MERGE-SORT(A, q+1, r)

    MERGE(A, p, q, r)

Complexity Analysis:

• Merge step: $\Theta(n)$.

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

• By Master Theorem (Case 2): $$\displaystyle \boxed{T(n) = \Theta(n \log n)} $$.

• Space: $\Theta(n)$ auxiliary for merging.

Quicksort

Algorithm:

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

2. Conquer: Recursively sort left and right subarrays.

Pseudocode:

QUICKSORT(A, p, r)

  if p < r

    q = PARTITION(A, p, r)

    QUICKSORT(A, p, q-1)

    QUICKSORT(A, q+1, r)

Average Case Analysis ($\Theta(n \log n)$):

• Let $C(n)$ be number of comparisons.

• For random pivot, expected comparisons: $$\displaystyle C(n) = n-1 + \frac{1}{n} \sum_{k=0}^{n-1} (C(k) + C(n-1-k)) $$.

• Solving recurrence yields $$\displaystyle C(n) \approx 1.39 n \ln n = \Theta(n \log n) $$.

Recurrence Relation:

• Worst Case: $$\displaystyle T(n) = T(n-1) + \Theta(n) \implies T(n) = \Theta(n^2) $$.

• Best/Avg Case: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) \implies T(n) = \Theta(n \log n) $$.

[!TIP] Exam Tip: For Quicksort, always clarify which case (best/avg/worst) you are analyzing.

Strassen's Matrix Multiplication

Algorithm (for two $n \times n$ matrices, $n$ a power of 2):

1. Divide each matrix into 4 submatrices of size $n/2 \times n/2$.

2. Compute 7 products (instead of 8) recursively:

$$ \begin{align*} M_1 &= (A_{11}+A_{22})(B_{11}+B_{22}) \\ M_2 &= (A_{21}+A_{22})B_{11} \\ M_3 &= A_{11}(B_{12}-B_{22}) \\ M_4 &= A_{22}(B_{21}-B_{11}) \\ M_5 &= (A_{11}+A_{12})B_{22} \\ M_6 &= (A_{21}-A_{11})(B_{11}+B_{12}) \\ M_7 &= (A_{12}-A_{22})(B_{21}+B_{22}) \end{align*} $$

3. Combine to get result submatrices:

$$ \begin{align*} C_{11} &= M_1 + M_4 - M_5 + M_7 \\ C_{12} &= M_3 + M_5 \\ C_{21} &= M_2 + M_4 \\ C_{22} &= M_1 - M_2 + M_3 + M_6 \end{align*} $$

Complexity Analysis:

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

• By Master Theorem (Case 1, $$\displaystyle \log_2 7 \approx 2.81 > 2 $$):

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

• Faster than naive $$\displaystyle O(n^3) $$ but larger constant factors; practical for large $n$.

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.

• Proof of Correctness: Must prove both properties. Often done by:

  1. Showing greedy choice is safe (leads to optimal solution).

  2. Using induction/contradiction on remaining subproblem.

Job Sequencing with Deadlines

Problem: Given $n$ jobs, each with profit $$\displaystyle P_i $$ and deadline $$\displaystyle d_i $$ (1 unit time per job). Maximize total profit by scheduling at most one job per time slot before its deadline.

Greedy Algorithm:

1. Sort jobs in decreasing order of profit.

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

3. For each job in sorted order:

   • Find latest available slot j (from min(d_i, max_deadline) down to 1) that is empty.

   • If found, schedule job in that slot.

Example (June 2024): $$\displaystyle n=4 $$, $$\displaystyle P = [100, 10, 15, 27] $$, $$\displaystyle d = [2, 1, 2, 1] $$.

• Sorted by profit: Job1(P100,d2), Job4(P27,d1), Job3(P15,d2), Job2(P10,d1).

• Slot assignment:

  • Job1 → slot 2 (latest ≤ d2).

  • Job4 → slot 1 (latest ≤ d1).

  • Job3 → no slot (d2 slots full).

  • Job2 → no slot (d1 slot full).

• Optimal Profit = 100 + 27 = 127.

Fractional Knapsack Problem

Problem: Fill knapsack of capacity $W$ with items having weight $$\displaystyle w_i $$, value $$\displaystyle v_i $$ (can take fractions). Maximize total value.

Greedy Algorithm:

1. Compute value/weight ratio $$\displaystyle r_i = v_i / w_i $$ for each item.

2. Sort items in decreasing order of $$\displaystyle r_i $$.

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

Example (June 2024): $$\displaystyle n=7 $$, $$\displaystyle W=15 $$, $$\displaystyle P=[10,5,15,7,6,18,3] $$, $$\displaystyle Wt=[2,3,5,7,1,4,1] $$.

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

• Sorted: Item5(r6), Item6(r4.5), Item1(r5), Item3(r3), Item7(r3), Item2(r1.67), Item4(r1).

• Take: Item5 (1 kg, value 6), Item6 (4 kg, value 18), Item1 (2 kg, value 10), Item3 (5 kg, value 15), Item7 (1 kg, value 3), Item2 (2 kg of 3? Wait capacity left: 15-1-4-2-5-1=2. Take 2/3 of Item2: value (2/3)*5=3.33).

• Total Value ≈ 6+18+10+15+3+3.33 = 55.33.

Example (Dec 2024): $$\displaystyle n=5 $$, $$\displaystyle W=10 $$, $$\displaystyle P=[10,15,10,12,8] $$, $$\displaystyle Wt=[3,3,2,5,1] $$.

• Ratios: [3.33, 5, 5, 2.4, 8].

• Sorted: Item5(r8), Item2(r5), Item3(r5), Item1(r3.33), Item4(r2.4).

• Take: Item5 (1 kg, 8), Item2 (3 kg, 15), Item3 (2 kg, 10), Item1 (3 kg of 3? Capacity left: 10-1-3-2=4. Take 3 kg of Item1: value 10). Total = 8+15+10+10 = 43.

• Optimal Value = 43.

Huffman Coding

Problem: Construct a binary prefix code for a set of symbols with given frequencies to minimize expected code length.

Greedy Algorithm:

1. Create a min-heap (priority queue) of nodes, each with symbol and frequency.

2. While heap size > 1:

   • Extract two nodes with smallest frequencies.

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

   • Insert new node into heap.

3. The remaining node is root of Huffman tree.

4. Traverse tree to assign codes (left=0, right=1).

Example:

Symbols: A(45), B(13), C(12), D(16), E(9), F(5).

• Steps: Merge F(5)+E(9)=14; Merge C(12)+D(16)=28? Wait, after first merge: nodes: A45, B13, C12, D16, (F+E)14. Next two smallest: B13 and (F+E)14 → 27. Then C12 and D16 → 28. Then 27+28=55. Then 45+55=100. Tree built.

• Codes: A:0, B:101, C:100, D:111, E:1101, F:1100. (Lengths: 1,3,3,3,4,4). Optimal.

Optimal Merge Patterns

Problem: Given sorted files of lengths $$\displaystyle L_1, L_2, ..., L_n $$, merge them two at a time. Cost to merge two files of lengths $a,b$ is $a+b$. Find merging order minimizing total cost.

Greedy Algorithm: Always merge the two smallest files first (using min-heap). Equivalent to constructing Huffman tree with file lengths as frequencies.

Example (Dec 2024):

Files: 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.

• Optimal Total Cost = 190.

Single Source Shortest Path – Dijkstra's Algorithm

Problem: Find shortest paths from source vertex $s$ to all other vertices in a graph with non-negative edge weights.

Algorithm:

1. Initialize distance array dist[]: dist[s]=0, others = ∞.

2. Create min-priority queue Q keyed by dist, insert all vertices.

3. While Q not empty:

   • Extract vertex u with minimum dist[u].

   • For each neighbor v of u:

     • If dist[u] + weight(u,v) < dist[v]:

       • dist[v] = dist[u] + weight(u,v)

       • Decrease-key in Q.

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

Application (June & Dec 2024): Given a graph, apply step-by-step. Key: always pick unvisited vertex with smallest tentative distance.

Minimum Spanning Tree – Kruskal's Algorithm

Problem: Find a spanning tree of a connected, undirected graph with minimum total edge weight.

Algorithm:

1. Sort all edges in non-decreasing order of weight.

2. Initialize MST as empty, and a disjoint-set (Union-Find) for vertices.

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

   • If find(u) != find(v) (adding edge doesn't form cycle):

     • Add edge to MST.

     • union(u,v).

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

Complexity: Dominated by sorting: $O(E \log E)$ or $O(E \log V)$.

Example (Dec 2024): Given graph with weighted edges, list edges sorted, then add if no cycle (using Union-Find).

IV. Dynamic Programming

Core Principles

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

• Overlapping Subproblems: Problem can be broken down into subproblems which are reused multiple times (vs. Divide & Conquer's distinct subproblems).

• Key Idea: Solve each subproblem once, store solution in a table (memoization or tabulation).

Multistage Graph Problem

Problem: Given a directed acyclic graph (DAG) with stages, find shortest path from start vertex $s$ to end vertex $t$.

DP Formulation:

• Let $cost(i)$ = shortest distance from vertex $i$ to $t$.

• Recurrence: $$\displaystyle cost(i) = \min_{j \in \text{ successors of } i} \{ \text{weight}(i,j) + cost(j) \} $$.

• Base: $$\displaystyle cost(t) = 0 $$.

• Compute in reverse topological order.

Algorithm:

MULTISTAGE-GRAPH(G, s, t)

  cost[t] = 0

  for i in reverse topological order (excluding t)

    cost[i] = min{ weight(i,j) + cost[j] for all j adjacent to i }

  return cost[s]

Computing Time: $O(V + E)$ if graph represented appropriately (each edge examined once).

Floyd-Warshall Algorithm

Problem: All-Pairs Shortest Paths in a weighted graph (can handle negative weights, no negative cycles).

Algorithm:

• Let $$\displaystyle D^{(k)}_{ij} $$ = shortest path from $i$ to $j$ using only intermediate vertices in $\{1,2,...,k\}$.

• Recurrence: $$\displaystyle D^{(k)}_{ij} = \min( D^{(k-1)}_{ij}, D^{(k-1)}_{ik} + D^{(k-1)}_{kj} ) $$.

• Initialize $$\displaystyle D^{(0)}_{ij} = \text{weight}(i,j) $$ (∞ if no edge, 0 if i=j).

Pseudocode:

FLOYD-WARSHALL(W)

  n = number of vertices

  D = W (copy)

  for k = 1 to n

    for i = 1 to n

      for j = 1 to n

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

  return D

Complexity: $$\displaystyle \boxed{\Theta(n^3)} $$ time, $$\displaystyle \Theta(n^2) $$ space.

Example (June 2024): Given adjacency matrix, apply triple loop step-by-step for $$\displaystyle k=1,2,... $$.

Reliability Design Problem

Problem: Design a system with $n$ stages. Each stage $i$ can use device type $j$ with cost $$\displaystyle c_{ij} $$ and reliability $$\displaystyle r_{ij} $$. Maximize overall reliability $$\displaystyle \prod_{i=1}^n r_{ij_i} $$ subject to total cost $\leq C$.

DP Approach:

• Let $R[i][c]$ = maximum reliability achievable for first $i$ stages with cost exactly $c$.

• Recurrence: $$\displaystyle R[i][c] = \max_{j: c_{ij} \leq c} \{ r_{ij} \times R[i-1][c - c_{ij}] \} $$.

• Base: $$\displaystyle R[0][c] = 1 $$ for $c \geq 0$ (no stages, reliability 1), $$\displaystyle R[0][c]=0 $$ for $$\displaystyle c<0 $$ (invalid).

• Compute for $$\displaystyle i=1 $$ to $n$, $$\displaystyle c=0 $$ to $C$.

• Answer: $$\displaystyle \max_{c \leq C} R[n][c] $$.

Example (Dec 2024): 3 stages, devices: D1(c30,r0.9), D2(c15,r0.8), D3(c20,r0.5). Budget $$\displaystyle C=105 $$.

• Build table $R[3][106]$.

• For stage1: $$\displaystyle R[1][c] = \max $$ over devices with cost ≤c.

  • $$\displaystyle R[1][30]=0.9 $$, $$\displaystyle R[1][15]=0.8 $$, $$\displaystyle R[1][20]=0.5 $$, others 0.

• For stage2: combine with stage1 choices.

  • e.g., $$\displaystyle R[2][45] = \max\{ r_{2j} \times R[1][45-c_{2j}] \} = \max\{0.8 \times R[1][30]=0.72, 0.5 \times R[1][25]=0, ...\}=0.72 $$.

• Continue for stage3.

• Find max $R[3][c]$ for $c \leq 105$.

V. Backtracking

Graph Coloring Problem (m-coloring)

Problem: Color vertices of graph with at most $m$ colors such that no two adjacent vertices have same color.

Backtracking Algorithm:

M-COLORING(graph, m)

  color[1..n] = {0}

  return COLOR(1)

COLOR(k)

  for c = 1 to m

    if SAFE(k, c)  // no neighbor colored c

      color[k] = c

      if k == n

        return true

      if COLOR(k+1)

        return true

      color[k] = 0  // backtrack

  return false

n-Queens Problem

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

Backtracking Algorithm:

N-QUEENS(n)

  board[1..n][1..n] = {0}

  return PLACE(1)

PLACE(row)

  if row > n

    return true

  for col = 1 to n

    if SAFE(row, col)  // no queen in same col, diag

      board[row][col] = 1

      if PLACE(row+1)

        return true

      board[row][col] = 0  // backtrack

  return false

SAFE(row, col): Check column col and both diagonals for any queen in rows 1..row-1.

Example (4-Queen, June 2024):

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

• Step-by-step backtracking tree.

Example (8-Queen, Dec 2024): One solution: [1,5,8,6,3,7,2,4] (row1 col1, row2 col5, etc.).

Hamiltonian Cycle

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

Backtracking Algorithm:

HAMILTONIAN(path, pos)

  if pos == n+1

    if edge exists from path[pos-1] to path[1]

      print path

    return

  for v = 1 to n

    if v not in path[1..pos-1] and edge exists from path[pos-1] to v

      path[pos] = v

      HAMILTONIAN(path, pos+1)

      path[pos] = 0  // backtrack

Start with path[1]=start_vertex.

Example (Dec 2024): Given graph, show recursive calls and backtracking when dead end reached.

VI. Branch and Bound

Traveling Salesperson Problem (TSP)

Problem: Given complete weighted graph, find minimum cost Hamiltonian cycle.

Branch and Bound Approach:

1. Reduction Method (Cost Matrix):

   • For each row, subtract row minimum.

   • For each column, subtract column minimum.

   • Sum of all subtracted values = initial bound.

2. State Space Tree: Each node represents a partial path (e.g., 1→2→3).

3. Bounding Function: For partial path ending at vertex $i$, compute reduced cost matrix after fixing edges in path, then add row/col reductions. This gives lower bound for any tour extending this path.

4. Search Strategy: Use best-first (priority queue by bound) or depth-first with pruning.

5. Prune: If bound ≥ best solution found so far, discard node.

Example (June & Dec 2024):

Given cost matrix (Dec 2024):

$$ \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} $$

• Step 1: Reduce matrix (row/col min subtraction).

• Step 2: Start from vertex 1 (assume fixed start). Explore children (to 2,3,4,5).

• For each child, compute bound by reducing matrix after fixing edge (1→child).

• Use priority queue to expand node with smallest bound.

• Continue until complete tour found, update best cost, prune others.

VII. Complexity Theory

Complexity Classes

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

  • Example: Sorting, Shortest Path (Dijkstra).

• NP: Decision problems where a "yes" instance has a polynomial-size certificate verifiable in polynomial time.

  • Example: TSP (given a tour, verify cost ≤ K in poly time).

• NP-Hard: Problems at least as hard as hardest problems in NP. Not necessarily in NP.

  • Example: Halting Problem, Optimization version of TSP.

• NP-Complete: Problems in NP and NP-Hard. If any NPC solved in poly time, P=NP.

  • Example: Boolean Satisfiability (SAT), Vertex Cover, Subset Sum.

Relationships:

$$ \boxed{P \subseteq NP \quad \text{and} \quad NP\text{-Complete} \subseteq NP\text{-Hard}} $$

• NPC = NP ∩ NP-Hard.

• Unknown: $$\displaystyle P = NP $$? (Most believe $P \neq NP$).

Reductions

• Concept: Transform problem $A$ into problem $B$ in polynomial time. If $B$ is solved, $A$ is solved.

• Use in NP-Completeness: To prove $X$ is NP-Hard, reduce a known NP-Hard problem (e.g., SAT) to $X$ in poly time. If $X \in NP$, then $X$ is NP-Complete.

• Types: Many-one reduction (Karp), Turing reduction.

VIII. Advanced Data Structures

B-trees

Definition: Self-balancing search tree where each node can have multiple keys and multiple children. Order $m$ B-tree:

• Each node has at most $m$ children.

• Each internal node (except root) has at least $\lceil m/2 \rceil$ children.

• Each node with $k$ children has $k-1$ keys.

• All leaves at same depth.

Properties:

• Height $$\displaystyle h = O(\log_m n) $$.

• Used for disk-based storage (databases, filesystems) due to high fanout reducing I/O.

Creation Process (Insertion):

1. Start at root, traverse to appropriate leaf.

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

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

   • Median key moves up to parent.

   • Leaf splits into two nodes with $\lfloor (m-1)/2 \rfloor$ keys each.

   • If parent full, split recursively (may increase height).

Example (June 2024): Insert sequence into B-tree of order 3 (2-3 tree). Show splits step-by-step.

IX. Specialized Topics (Short Notes)

Data Stream Algorithms

• Process data as a stream (one pass, limited memory).

• Key Problems: Finding frequent items (Misra-Gries), estimating moments (AMS), distinct elements (HyperLogLog).

• Core Idea: Use randomized algorithms with small space (sublinear in $n$).

• Example: Count-Min Sketch for frequency estimation.

Approximation Algorithms

• For NP-Hard optimization problems, find solutions close to optimal in polynomial time.

• Performance Ratio: $\rho \geq 1$ s.t. $$\displaystyle cost_{approx} \leq \rho \cdot cost_{opt} $$.

• Examples: Vertex Cover (2-approx), TSP with triangle inequality (1.5-approx via MST), Knapsack (FPTAS).

• Techniques: Greedy, LP relaxation, rounding.

Data Transfer Optimization

• Minimize cost/time for transferring data in networks/distributed systems.

• Problems: File transfer scheduling, multicast, replication.

• Algorithms: Use Huffman coding for optimal merge patterns (as in Dec 2024), or network flow techniques.

• Example: Transfer files of sizes $$\displaystyle L_i $$ to a central server; minimize total transfer time by merging files optimally.

Logic Optimization

• Minimize Boolean function representation (e.g., sum-of-products).

• Techniques: Karnaugh maps (manual), Quine-McCluskey (tabular), Espresso (heuristic).

• Applications: Digital circuit design, compiler optimization.

• Key Concepts: Prime implicants, essential primes, covering problem.

Design and Complexity of Parallel Algorithms

• Design algorithms for multiple processors (PRAM model).

• Goals: Minimize time (parallel time) and work (time × processors).

• Key Metrics: Speedup $$\displaystyle S = T_{seq}/T_{par} $$, Efficiency $$\displaystyle E = S/p $$.

• Examples: Parallel merge sort (divide & conquer), parallel prefix sum.

• Complexity Classes: NC (problems efficiently parallelizable), P-complete (hard to parallelize).

• Challenges: Load balancing, synchronization, communication overhead.

END OF UNIT 1 NOTES