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

UNIT 2: Algorithmic Paradigms and Advanced Topics

I. Fundamentals of Algorithm Analysis

A. Time Complexity and Space Complexity

• Time Complexity: Measures the amount of time an algorithm takes to run as a function of the input size n. It is expressed using asymptotic notations.

• Space Complexity: Measures the amount of memory (space) an algorithm uses as a function of the input size n. It includes both auxiliary space (extra space used) and input space.

B. Asymptotic Notations

Used to describe the limiting behavior of a function and classify algorithms by their growth rates.

[!TIP] Exam Focus

• O is most commonly used for worst-case analysis.

• For a given function, finding Θ is ideal as it gives the precise complexity.

• Remember: $O$ is $\le$, $\Omega$ is $\ge$, $\Theta$ is $$\displaystyle = $$ (up to constant factors).

C. Recurrence Relations

Equations that define a sequence based on its previous terms. Essential for analyzing recursive algorithms.

1. Solving Recurrences

• Substitution Method: Guess the solution and prove it by mathematical induction.

• Recursion Tree Method: Visualize the recurrence as a tree, sum costs at each level, and sum over all levels.

• Master Theorem: For recurrences of the form $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $$\displaystyle a \ge 1, b > 1 $$:

$$ T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{if } f(n) = O(n^{\log_b a - \epsilon}) \text{ for some } \epsilon > 0 \text{ (Case 1)} \\ \Theta(n^{\log_b a} \log n) & \text{if } f(n) = \Theta(n^{\log_b a}) \text{ (Case 2)} \\ \Theta(f(n)) & \text{if } f(n) = \Omega(n^{\log_b a + \epsilon}) \text{ and } af(n/b) \le cf(n) \text{ for some } c < 1 \text{ (Case 3)} \end{cases} $$

2. Application to Sorting

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

• QuickSort:

  • Best/Average Case (balanced partition): $$\displaystyle T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n) $$.

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

II. Divide and Conquer

A. General Approach

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

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

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

B. Merge Sort

Algorithm:

1. If n <= 1, return array.

2. Divide: Find middle index mid = n/2.

3. Conquer: Recursively sort left half L[0..mid-1] and right half R[mid..n-1].

4. Combine: Merge the two sorted halves.

Complexity Analysis:

• Time: Splitting is $O(1)$, merging is $O(n)$. Recurrence: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) $$. Solution: $\boxed{\Theta(n \log n)}$.

• Space: Requires $O(n)$ auxiliary space for merging.

C. Quick Sort

1. Algorithm & Partitioning

Algorithm:

1. Choose a pivot element from the array.

2. Partition: Rearrange the array so that all elements < pivot are on the left, all > pivot on the right. Pivot is in its final sorted position.

3. Recursively apply the above steps to the left and right sub-arrays.

Partition Scheme (Lomuto):

partition(A, low, high):

    pivot = A[high]

    i = low - 1

    for j = low to high-1:

        if A[j] <= pivot:

            i = i + 1

            swap A[i] and A[j]

    swap A[i+1] and A[high]

    return i+1

2. Average Case Time Complexity: $O(n \log n)$

• At each level of recursion, the n elements are processed in $O(n)$ time (partitioning).

• On average, the pivot splits the array into two roughly equal parts ($\approx n/2$).

• The recursion tree has height $\log n$.

• Total work: $$\displaystyle O(n) \times \text{height} = O(n \log n) $$.

3. Worst and Best Case

• Worst Case ($$\displaystyle O(n^2) $$): Occurs when the pivot is consistently the smallest or largest element (e.g., already sorted array with first/last element as pivot). Recursion tree height becomes $n$.

• Best Case ($O(n \log n)$): Occurs when the pivot is always the median, splitting the array into two equal halves.

[!TIP] Common Pitfall

• Do not confuse the worst-case of QuickSort ($$\displaystyle O(n^2) $$) with its average-case ($O(n \log n)$). The average case assumes a random pivot or a reasonably balanced split on average.

D. Strassen's Matrix Multiplication

1. Algorithm Steps

For two $n \times n$ matrices $A$ and $B$ (assuming $n$ is a power of 2):

1. Divide each matrix into four $n/2 \times n/2$ sub-matrices.

2. Compute the following 7 products (instead of 8):

   • $$\displaystyle M_1 = (A_{11} + A_{22}) \times (B_{11} + B_{22}) $$

   • $$\displaystyle M_2 = (A_{21} + A_{22}) \times B_{11} $$

   • $$\displaystyle M_3 = A_{11} \times (B_{12} - B_{22}) $$

   • $$\displaystyle M_4 = A_{22} \times (B_{21} - B_{11}) $$

   • $$\displaystyle M_5 = (A_{11} + A_{12}) \times B_{22} $$

   • $$\displaystyle M_6 = (A_{21} - A_{11}) \times (B_{11} + B_{12}) $$

   • $$\displaystyle M_7 = (A_{12} - A_{22}) \times (B_{21} + B_{22}) $$

3. Combine to get the four quadrants of the result matrix $C$:

   • $$\displaystyle C_{11} = M_1 + M_4 - M_5 + M_7 $$

   • $$\displaystyle C_{12} = M_3 + M_5 $$

   • $$\displaystyle C_{21} = M_2 + M_4 $$

   • $$\displaystyle C_{22} = M_1 - M_2 + M_3 + M_6 $$

2. Complexity Analysis

Recurrence: $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$ (7 recursive calls, each of size $n/2$, plus $$\displaystyle O(n^2) $$ for additions).

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

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

This is asymptotically faster than the naive $$\displaystyle O(n^3) $$ method.

III. Greedy Algorithms

A. Key Properties

1. Greedy Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice at each step without reconsidering previous choices.

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

[!TIP] Critical Distinction

• Greedy makes one irrevocable choice per step. Dynamic Programming explores all possible choices (via subproblem solutions) and picks the best.

• To prove a greedy algorithm correct, you must prove BOTH properties.

B. Standard Greedy Algorithms

1. Job Sequencing with Deadlines

Problem: Maximize total profit for jobs with deadlines (1 unit time each) and profits. Schedule at most one job per time slot. Algorithm:

1. Sort all jobs in decreasing order of profit.

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

3. For each job in sorted order:

   • Find the latest available time slot t that is <= job.deadline.

   • If such a slot exists, assign the job to slot[t] and mark it filled.

4. Output the scheduled jobs.

Example (Jun 2024):

Jobs: (P,d) = (100,2), (10,1), (15,2), (27,1)

Sorted by Profit: J1(100,2), J4(27,1), J3(15,2), J2(10,1)

• J1 → slot 2 (latest ≤2).

• J4 → slot 1 (latest ≤1).

• J3 → no slot (2 is taken, 1 is taken).

• J2 → no slot. Optimal Solution: Jobs 1 and 4, Total Profit = 127.

2. Fractional Knapsack Problem

Problem: Fill a knapsack of capacity W with items having weight w_i and value v_i to maximize total value. Items can be broken (fractional). Greedy Choice: Pick items in decreasing order of value/weight ratio ($$\displaystyle v_i/w_i $$). Take whole item if possible, else take a fraction. Complexity: $O(n \log n)$ due to sorting. Note: 0/1 Knapsack is NOT solvable by a greedy algorithm (it's a DP problem).

3. Huffman Coding

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

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

2. While there is more than one node in the heap:

   • Extract two nodes with the smallest frequencies.

   • Create a new internal node with these two as children and frequency = sum.

   • Insert the new node back into the heap.

3. The remaining node is the root of the Huffman Tree. Complexity: $O(n \log n)$.

4. Optimal Merge Pattern

Problem: Given n sorted files of lengths $$\displaystyle L_1, L_2, ..., L_n $$, find the optimal way to merge them into one file with minimum total computation (cost of merging two files of lengths a and b is a+b). Greedy Choice: Always merge the two smallest available files first. Algorithm: Use a min-heap. Repeatedly extract two smallest, merge them, and insert the sum back. Complexity: $O(n \log n)$. Relation to Huffman: Identical structure. File lengths are analogous to symbol frequencies.

C. Graph Algorithms

1. Minimum Spanning Tree (MST) - Kruskal's Algorithm

Problem: Find a subset of edges that connects all vertices with minimum total weight and without cycles. Algorithm:

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

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

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

   • If Find(u) != Find(v) (adding edge does not form a cycle):

     • Add edge to MST.

     • Union(u, v).

4. Stop when MST has V-1 edges. Complexity: $O(E \log E)$ or $O(E \log V)$ dominated by sorting.

2. Single Source Shortest Path - Dijkstra's Algorithm

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

1. Initialize dist[s] = 0, dist[v] = ∞ for all others. Create a min-priority queue Q keyed by dist.

2. While Q is not empty:

   • Extract vertex u with minimum dist[u].

   • For each neighbor v of u:

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

     • If alt < dist[v]: update dist[v] = alt and prev[v] = u; decrease-key in Q. Complexity: $O((V+E) \log V)$ with binary heap; $O(E + V \log V)$ with Fibonacci heap.

[!WARNING] Limitation: Fails with negative edge weights. Use Bellman-Ford instead.

IV. Dynamic Programming (DP)

A. Core Principles

1. Optimal Substructure: An optimal solution to the problem can be constructed from optimal solutions to its subproblems.

2. Overlapping Subproblems: The problem can be broken down into subproblems which are reused multiple times (unlike Divide & Conquer).

3. Memoization (Top-Down): Recursive solution that stores results of subproblems in a table (cache) to avoid recomputation.

4. Tabulation (Bottom-Up): Iterative solution that fills a DP table in a specific order (usually increasing problem size).

DP vs Greedy: Greedy makes one choice. DP evaluates all feasible choices for each subproblem and picks the best.

B. Applications

1. 0/1 Knapsack Problem

Problem: Given n items (weight w_i, value v_i) and knapsack capacity W, select a subset (0 or 1 of each) to maximize total value without exceeding W. DP State: dp[i][w] = maximum value using first i items with capacity w. Recurrence:

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

Complexity: $O(nW)$ time and space. Space can be optimized to $O(W)$.

2. Single Source Shortest Path - Bellman-Ford Algorithm

Problem: SSSP in a graph with negative edge weights (but no negative cycles). Algorithm:

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

2. Relax all edges |V|-1 times:

   • For each edge (u, v) with weight w: if dist[u] + w < dist[v], update dist[v].

3. (Optional) Check for negative cycles by relaxing all edges once more. If any distance updates, a negative cycle exists. Complexity: $O(VE)$. Key Feature: Can detect negative-weight cycles reachable from source.

3. All Pairs Shortest Path - Floyd-Warshall Algorithm

Problem: Find shortest paths between every pair of vertices. Algorithm:

1. Initialize distance matrix dist with direct edge weights (∞ if no edge, 0 on diagonal).

2. For k from 1 to V:

   • For every pair (i, j):

     • dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) Complexity: $$\displaystyle O(V^3) $$. Simple and works with negative edges (no negative cycles). Output: dist[i][j] gives shortest path length. Can be modified to store the path (via next matrix).

4. Reliability Design Problem

Problem: Design a system with n stages. Stage i has m_i device types with cost c_{ij} and reliability r_{ij}. Maximize overall system reliability $$\displaystyle \prod_{i=1}^{n} r_{ij_i} $$ subject to total cost $\le C$. DP Approach:

• State: R[i][c] = maximum reliability achievable for the first i stages with total cost exactly c.

• Recurrence: R[i][c] = max_{j} { R[i-1][c - c_{ij}] * r_{ij} } for all device types j in stage i where c_{ij} <= c.

• Answer: max_{c <= C} R[n][c]. Complexity: $$\displaystyle O(n \cdot C \cdot \max(m_i)) $$.

5. Multistage Graph Problem

Problem: Find the minimum cost path from a start vertex s (stage 1) to a terminal vertex t (stage n) in a directed acyclic graph (DAG) where vertices are partitioned into stages. DP Approach (Forward/Backward):

• Let cost(i, v) be min cost from vertex v in stage i to t.

• Base: cost(n, t) = 0.

• Recurrence (backward): cost(i, v) = min_{w \in Adj(v)} { c(v,w) + cost(i+1, w) }.

• Answer: cost(1, s). Complexity: $O(V + E)$.

V. Backtracking

A. State Space Tree and Pruning

• State Space Tree: Represents all possible solutions (configurations). Each node is a partial solution (a choice at a certain level).

• Pruning: Systematically abandoning (pruning) branches of the tree that cannot lead to a feasible or optimal solution.

• Key Idea: Explore the tree depth-first. At each node, check if the partial solution can be extended to a full solution. If not, backtrack to the parent node and try the next alternative.

B. Applications

1. Graph Coloring (m-coloring)

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

graphColoring(graph G, int m):

    color[1..V] = {0}  // 0 means uncolored

    return solve(0)    // start with vertex 0

solve(v):

    if v == V: return true  // all colored

    for c = 1 to m:

        if isSafe(v, c):     // check neighbors

            color[v] = c

            if solve(v+1): return true

            color[v] = 0     // backtrack

    return false

isSafe(v, c): Check all adjacent vertices of v. If any has color c, return false.

2. N-Queens Problem

Problem: Place N queens on an N×N chessboard so no two attack each other (no same row, column, or diagonal). Backtracking Approach:

• Place queens one row at a time.

• State: row index, and col[1..N] array where col[i] is column of queen in row i.

• Recursive Step: For current row r, try each column c. Check if placing at (r,c) is safe against all previously placed queens (i, col[i]) for i < r.

  • Safe if: c != col[i] (column) and |r - i| != |c - col[i]| (diagonal).

• If safe, place queen and recurse for row r+1. If all rows placed, solution found.

3. Hamiltonian Cycle Problem

Problem: Find a cycle in an undirected graph that visits every vertex exactly once and returns to start. Backtracking Approach:

• State: path[0..V-1] storing the current vertex path, and pos (current position).

• Base: If pos == V, check if last vertex has an edge to path[0]. If yes, Hamiltonian Cycle found.

• Recursive Step: For current vertex path[pos-1], try all adjacent vertices v that are not already in path[0..pos-1].

  • Add v to path[pos] and recurse for pos+1.

  • On failure, remove v from path (backtrack).

VI. Branch and Bound

A. Core Concept

• State Space Tree: Like backtracking, but nodes represent partial solutions.

• Bounding Function: A function that computes a bound (e.g., cost, profit) on the best possible solution that can be obtained from a given node/partial solution.

• Best-First Search: Uses a priority queue (e.g., min-heap for minimization) to explore the most promising node (lowest bound) next.

• Pruning: If the bound of a node is worse than the best complete solution found so far (best), discard the node and its subtree.

B. Travelling Salesman Problem (TSP)

1. Reduction Method (Cost Matrix Reduction)

To get a tighter initial bound and simplify the matrix:

1. Row Reduction: For each row, subtract the minimum element in that row from all elements in the row.

2. Column Reduction: For each column, subtract the minimum element in that column from all elements in the column.

3. The sum of all subtracted minima is the initial lower bound for the path starting from the current node.

4. The reduced matrix is used for further branching.

2. Algorithm & Example

Algorithm:

1. Start with the root node (complete cost matrix). Reduce it, get bound B.

2. Initialize best = ∞. Create a min-priority queue Q ordered by bound.

3. While Q not empty:

   • Extract node N with minimum bound.

   • If N.bound >= best: prune (discard N and its subtree).

   • If N represents a complete tour (path length = n+1): update best = min(best, N.bound).

   • Else, branch on the next possible vertex j not in N.path:

     • Create child node by adding edge (i, j) to path.

     • Set child's cost = N.cost + reduced_cost(i,j).

     • Reduce the child's matrix (set row i and col j to ∞, set (j,i) to ∞ to avoid subtour).

     • Compute child's bound = child.cost + sum(row_mins) + sum(col_mins).

     • If child.bound < best, insert child into Q.

4. best is the optimal tour cost.

[!TIP] Exam Strategy

• For TSP, clearly show the reduced matrix at each node.

• The bound = cost so far + sum of all row minima + sum of all column minima of the reduced matrix.

• Always prune nodes with bound >= best_solution_so_far.

VII. Complexity Theory

A. Complexity Classes

B. Reductions and Completeness

• Polynomial-Time Reduction: Transforming problem A into problem B such that solving B efficiently implies solving A efficiently. Denoted $$\displaystyle A \le_p B $$.

• To prove a problem X is NP-Complete:

  1. Show X ∈ NP (give a polynomial-time verifier).

  2. Show X is NP-Hard: take a known NP-Complete problem Y and show $$\displaystyle Y \le_p X $$ in polynomial time.

C. Relationship between P, NP, NP-Hard, NP-Complete

[!IMPORTANT] The Million-Dollar Question

• P ⊆ NP (trivially, as any problem solvable in poly-time is also verifiable in poly-time).

• P = NP ? is the most famous open problem in computer science.

• NP-Complete = NP ∩ NP-Hard.

• If any NP-Complete problem has a polynomial-time solution, then P = NP.

VIII. Advanced Topics

A. B-trees

1. Properties and Structure

• A self-balancing tree data structure for disk-based storage (databases, file systems).

• Order m B-tree:

  • Every node (except root) has at least $\lceil m/2 \rceil$ children (and $\lceil m/2 \rceil - 1$ keys).

  • Every node has at most m children (and m-1 keys).

  • All leaves are at the same depth.

  • Keys in a node are sorted. A node with k children has k-1 keys, partitioning the children's key ranges.

  • Height is $$\displaystyle O(\log_m n) $$, very shallow.

2. Insertion and Deletion (Creation)

Insertion:

1. Find the appropriate leaf node L where the new key k belongs.

2. If L has < m-1 keys, insert k in sorted order.

3. If L is full (has m-1 keys):

   • Split L into two nodes, L1 and L2, each with $\lceil (m-1)/2 \rceil$ and $\lfloor (m-1)/2 \rfloor$ keys.

   • The median key is promoted to the parent.

   • Recursively split the parent if it becomes full.

   • If root splits, a new root is created (tree height increases by 1).

Deletion (from leaf/ internal node):

1. Find the key k to delete.

2. If k is in a leaf and leaf has > min_keys, simply remove it.

3. If k is in an internal node, replace it with its predecessor (max key in left subtree) or successor (min key in right subtree), then delete that key from the leaf.

4. If deletion causes a node to have < min_keys:

   • Redistribute (borrow a key from a sibling).

   • If siblings are also minimum, merge the underflow node with a sibling and a key from the parent.

   • Recursively fix parent if necessary.

   • If root loses its last key, delete root (height decreases).

B. Data Stream Algorithms

• Deal with data arriving as a stream (one pass or limited passes), where storing all data is infeasible.

• Goal: Compute synopses or sketches (small summaries) of the stream to answer approximate queries.

• Key Problems:

  • Counting Distinct Elements (Flajolet-Martin algorithm, HyperLogLog).

  • Frequent Items/Misra-Gries algorithm (find items occurring more than n/k times using O(k) space).

  • Quantiles/Heavy Hitters.

• Core Challenge: Space-time trade-off and approximation guarantees.

C. Approximation Algorithms

• For NP-Hard optimization problems, where finding the exact optimal solution is likely intractable.

• Provide a polynomial-time algorithm that returns a solution guaranteed to be within a certain factor of the optimal solution.

• Performance Ratio $\rho$: For a minimization problem, solution cost $$\displaystyle C_{approx} \le \rho \cdot C_{opt} $$.

• Examples:

  • Vertex Cover: 2-approximation (pick both endpoints of an arbitrary edge).

  • TSP with Triangle Inequality: 1.5-approximation (using MST doubling).

  • Set Cover: $O(\log n)$-approximation (greedy).

D. Data Transfer Optimization

• Often refers to problems in network flow or scheduling.

• Core Problem: Maximize throughput or minimize transfer time under constraints (bandwidth, latency, storage).

• Typical Model: A flow network with capacities. Goal is to compute maximum flow (Ford-Fulkerson, Edmonds-Karp) or minimum cost flow.

• Application: Bandwidth allocation, load balancing, file distribution (e.g., minimizing makespan in parallel download).

E. Logic Optimization

• Primarily from Digital Logic Design and VLSI.

• Goal: Simplify a Boolean function (given as a sum-of-products or circuit) to an equivalent form with fewer gates/wires and lower delay.

• Techniques:

  • Karnaugh Map (K-map): Manual grouping for up to 4-6 variables.

  • Quine-McCluskey Method: Tabular, systematic method for many variables.

  • Espresso Algorithm: Heuristic for large-scale logic minimization.

• Relation to Algorithms: Uses concepts like implicants, prime implicants, and covering problems (which can be modeled as set cover).

F. Parallel Algorithms (Design and Complexity)

• Design Paradigms:

  • Divide & Conquer (parallel merge sort, quick sort).

  • Pointer Jumping (for list ranking, tree problems).

  • Contraction (for graph problems like MST, connected components).

  • Euler Tour technique (for tree problems).

• Complexity Measures:

  • Work ($$\displaystyle T_1 $$): Total number of operations across all processors (sequential time).

  • Span ($$\displaystyle T_\infty $$): Longest path of dependent operations (critical path, parallel time).

  • Parallelism = $$\displaystyle T_1 / T_\infty $$ (maximum possible speedup).

• PRAM Model (Parallel Random Access Machine): Assumes shared memory, unit-cost access. Variants: CREW, CRCW.

• Goal: Design algorithms with low span (good parallelism) and efficient work (work-efficient: $$\displaystyle T_1 = O(T_{seq}) $$).

END OF UNIT 2 NOTES