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

UNIT 5: Analysis and Design of Algorithm - Short Notes

1. Fundamentals of Algorithm Analysis

Algorithm Design & Analysis Process

Flow: Problem → Design Technique → Algorithm → Analysis → Implementation → Testing → Maintenance.

• Design: Choose paradigm (Divide & Conquer, Greedy, DP, etc.).

• Analysis: Predict resources (Time, Space) using asymptotic notations.

• Implementation: Code in high-level language.

• Testing & Maintenance: Verify correctness, debug, optimize.

Asymptotic Notations (Bounding Functions)

[!TIP] Exam Tip: To prove $$\displaystyle f(n) = O(g(n)) $$, find constants $c$ and $$\displaystyle n_0 $$ such that inequality holds.

Time Complexity Analysis Types

• Worst-case: Maximum time over all inputs of size $n$. Most common for guarantees.

• Average-case: Expected time over all inputs (requires probability distribution).

• Best-case: Minimum time (often trivial, e.g., finding first element).

Trade-offs: Readability vs Optimization

• Optimize first for asymptotic complexity (Big O).

• Refactor later for readability if performance gain is marginal (< constant factor).

• Never sacrifice clarity for micro-optimizations unless profiling shows a bottleneck.

Recurrence Relations

Forming Recurrence: From recursive algorithm.

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

Solving Techniques:

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

2. Recursion Tree: Visualize cost per level, sum costs.

3. Master Theorem (for $$\displaystyle T(n)=aT(n/b)+f(n) $$):

$$\boxed{T(n) = \begin{cases} \Theta(n^{\log_b a}) & \text{if } f(n)=O(n^{\log_b a - \epsilon}) \\ \Theta(n^{\log_b a} \log n) & \text{if } f(n)=\Theta(n^{\log_b a}) \\ \Theta(f(n)) & \text{if } f(n)=\Omega(n^{\log_b a + \epsilon}) \text{ and } af(n/b) \leq cf(n) \end{cases}}$$

4. Complex Recurrences: Use recursion tree or iterative expansion.

   • Example: $$\displaystyle T(n)=n+T(n/10)+T(7n/5) $$. The term $T(7n/5)$ dominates → $$\displaystyle T(n) = \Theta(n) $$.

Lower Bound Theory

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

• Lower Bound for Sorting: $\Omega(n \log n)$ comparisons (height of decision tree with $n!$ leaves).

• Selection Sort (3 elements) Example:

  • Possible permutations: $$\displaystyle 3! = 6 $$ leaves.

  • Minimum height $h$: $$\displaystyle 2^h \geq 6 \Rightarrow h \geq \lceil \log_2 6 \rceil = 3 $$.

  • Hence, $\Omega(3)$ comparisons needed in worst-case.

2. Sorting Algorithms

General Comparison-based Lower Bound

$\boxed{\Omega(n \log n)}$ comparisons in worst-case (via decision tree).

Stable vs Unstable Sorting

Merge Sort (Divide & Conquer)

• Algorithm:

  1. Divide array into two halves.

  2. Recursively sort each half.

  3. Merge two sorted halves.

• Time Complexity: $$\displaystyle T(n) = 2T(n/2) + \Theta(n) \Rightarrow \boxed{\Theta(n \log n)} $$ (Master Theorem Case 2).

• Stable: Yes (if merge is implemented stably).

• Space: $O(n)$ auxiliary.

Quick Sort (Divide & Conquer)

• Algorithm:

  1. Choose pivot (first/last/random/median-of-three).

  2. Partition: Rearrange so elements < pivot left, > pivot right.

  3. Recursively sort left and right partitions.

• Complexity:

  • Worst-case (sorted input, bad pivot): $$\displaystyle T(n)=T(n-1)+\Theta(n) \Rightarrow \boxed{O(n^2)} $$.

  • Average-case (random pivot): $\boxed{O(n \log n)}$.

  • Best-case (balanced partitions): $O(n \log n)$.

• Unstable: Partitioning can swap equal elements.

• In-place: Yes (except recursion stack).

Heap Sort

• Algorithm:

  1. Build Max-Heap from array ($O(n)$).

  2. Repeatedly extract max (swap root with last element, heapify reduced heap).

• Time Complexity: Build heap $O(n)$ + $n$ extractions $\times$ heapify $O(\log n) \Rightarrow \boxed{O(n \log n)}$.

• Unstable: Heapify can reorder equal elements.

• In-place: Yes.

3. Divide and Conquer (Non-Sorting)

General Method & Control Abstraction

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

2. Conquer: Solve subproblems recursively (or directly if small).

3. Combine: Merge subproblem solutions.

Binary Search

• Recurrence: $$\displaystyle T(n) = T(n/2) + O(1) \Rightarrow \boxed{O(\log n)} $$.

• Algorithm: Compare target with middle element; recurse on left/right half.

Strassen's Matrix Multiplication

• Idea: Multiply two $2\times2$ matrices using 7 (not 8) recursive multiplications.

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

• Better than $$\displaystyle O(n^3) $$ for large $n$ (despite larger constant factors).

• Example (2×2):

  Given $$\displaystyle A=\begin{bmatrix} a & b \\ c & d \end{bmatrix}, B=\begin{bmatrix} e & f \\ g & h \end{bmatrix} $$.

  Compute 7 products:

  $$\displaystyle P_1 = a(f-h) $$, $$\displaystyle P_2 = (a+b)h $$, ..., $$\displaystyle P_7 = (c-a)(e+f) $$.

  Then combine: $$\displaystyle C_{11}=P_5+P_4-P_2+P_6 $$, etc.

Finding Max & Min in Array (Divide & Conquer)

• Recursive Approach:

  • Base: 1 element → that element is both min & max.

  • Base: 2 elements → compare, assign min & max.

  • Divide array into halves, get min/max from each, compare.

• Complexity: $$\displaystyle T(n)=2T(n/2)+2 \Rightarrow \boxed{\approx 3n/2 - 2} $$ comparisons (better than naive $2n-2$).

4. Greedy Algorithms

Key Properties for Correctness

1. Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.

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

[!TIP] Must prove BOTH for correctness. Greedy algorithms are not always optimal.

Minimum Spanning Tree (MST)

• Kruskal's Algorithm:

  1. Sort all edges by weight (ascending).

  2. Initialize forest (each vertex separate).

  3. Add edges in order, skip if forms cycle (use Union-Find data structure).

  4. Stop when $|V|-1$ edges added.

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

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

• Prim's Algorithm:

  1. Start with arbitrary vertex in MST.

  2. Grow MST by adding minimum weight edge connecting MST to a vertex outside.

  3. Use priority queue for min edge extraction.

  • Time: $$\displaystyle O(V^2) $$ (simple) or $O(E \log V)$ (with binary heap).

Job Sequencing with Deadlines

• Greedy Solution:

  1. Sort jobs by profit descending.

  2. Initialize slots [1..max_deadline] as empty.

  3. For each job, place it in the latest free slot $\leq$ its deadline.

• Example: $$\displaystyle n=4 $$, Profits=(100,10,15,27), Deadlines=(2,1,2,1).

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

  • Schedule: Slot2←Job1, Slot1←Job4. Total Profit = 127.

Fractional Knapsack

• Greedy by Profit/Weight Ratio.

• Algorithm: Sort items by $$\displaystyle p_i/w_i $$ descending. Take as much as possible of each until knapsack full (can take fractions).

• Example: $$\displaystyle n=7, W=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: 5(1),1(2),6(4),7(1) → weight=8, profit=10+5+18+3=36.

  • Remaining capacity=7. Next item3(w5): take full → weight=13, profit=51.

  • Next item2(w3): take $2/3$ → weight=15, profit=$51 + 10*(2/3) \approx 57.67$.

  • Optimal Profit ≈ 57.67.

Huffman Coding

• Greedy Tree Construction:

  1. Create leaf node for each symbol with probability $$\displaystyle p_i $$.

  2. While >1 node: Merge two nodes with smallest probabilities into new node (probability = sum).

  3. Assign 0/1 to left/right branches.

• Optimality: Minimizes expected code length $$\displaystyle L = \sum p_i \cdot l_i $$.

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

  • Huffman Tree: (

    DiagramCANVAS: Huffman tree merging smallest probabilities first: a+b=0.16, c+0.16=0.28, d+e=0.45, 0.28+f=0.55, 0.45+0.55=1.0
    )

  • Codes: f:0, d:10, e:110, c:1110, a:11110, b:11111.

  • Average Length: $$\displaystyle L = 0.27*1 + 0.22*2 + 0.23*3 + 0.12*4 + 0.07*5 + 0.09*5 = \boxed{2.26 \text{ bits/symbol}} $$.

Optimal Merge Pattern

• Problem: Merge $n$ sorted files with sizes $$\displaystyle s_1,...,s_n $$; cost of merging two files of size $x,y$ is $x+y$. Minimize total cost.

• Greedy Solution: Always merge two smallest files first (like Huffman).

• Example: 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 = 190.

Single Source Shortest Path (Dijkstra)

• Greedy: At each step, select vertex with smallest tentative distance.

• Algorithm:

  1. Initialize dist[source]=0, others=∞. Set all unvisited.

  2. While unvisited vertices exist:

     • Pick unvisited vertex $u$ with min dist.

     • For each neighbor $v$ of $u$: if dist[u] + weight(u,v) < dist[v], update dist[v].

• Time Complexity:

  • Simple array: $$\displaystyle O(V^2) $$.

  • Binary heap (priority queue): $O((E+V) \log V) \approx O(E \log V)$.

• Works only for non-negative weights.

5. Dynamic Programming

Key Principles

• Optimal Substructure: Global optimum = combination of optimal subproblem solutions.

• Overlapping Subproblems: Recursive algorithm solves same subproblems repeatedly → store solutions (memoization/tabulation).

0/1 Knapsack Problem

• Problem: $n$ items, profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$, capacity $W$. Each item 0 or 1.

• DP Table: $$\displaystyle dp[i][w] = $$ max profit using first $i$ items, 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}$$

• Algorithm (Bottom-up): Fill $n+1 \times W+1$ table row-wise.

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

  • Table:
    DiagramCANVAS: 5x43 table. Row1: all 0. Row2: w>=2: max(0,11+dp[1][w-2])=11. Row3: w>=12: max(prev,21+dp[2][w-12]). Row4: w>=23: max(prev,31+dp[3][w-23]). Row5: w>=15: max(prev,33+dp[4][w-15]). Final dp[4][42]=62 (items 1,3,4).

All-Pairs Shortest Paths (Floyd-Warshall)

• DP on intermediate vertices: $$\displaystyle D^{(k)}_{ij} = $$ shortest path from $i$ to $j$ using vertices $\{1..k\}$ as intermediates.

• Recurrence:

$$D^{(k)}_{ij} = \min\left(D^{(k-1)}_{ij}, \ D^{(k-1)}_{ik} + D^{(k-1)}_{kj}\right)$$

• Algorithm: Initialize $$\displaystyle D^{(0)}= $$ adjacency matrix. For $$\displaystyle k=1..n $$, for all $i,j$, update.

• Time Complexity: $$\displaystyle \boxed{O(n^3)} $$.

• Detects negative cycles (if $$\displaystyle D^{(n)}_{ii} < 0 $$).

Transitive Closure (Warshall's Algorithm)

• Special case of Floyd-Warshall for unweighted graphs (reachability).

• $$\displaystyle R^{(k)}_{ij} = R^{(k-1)}_{ij} \lor (R^{(k-1)}_{ik} \land R^{(k-1)}_{kj}) $$.

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

Multistage Graph (Shortest Path)

• Problem: Directed acyclic graph with stages $1..k$. Find shortest path from start (stage 1) to end (stage k).

• DP Approach (Forward):

  • $$\displaystyle f_k(v) = $$ cost of shortest path from $v$ to end.

  • $$\displaystyle f_k(\text{end}) = 0 $$.

  • $$\displaystyle f_k(v) = \min_{w \in \text{successors}(v)} \{ \text{cost}(v,w) + f_{k+1}(w) \} $$.

• Computing Time: $O(|V|+|E|)$ if topological order used.

Reliability Design

• Problem: Design $k$-stage system. Stage $i$ has device types with $$\displaystyle (cost_i, reliability_i) $$. Maximize total reliability $$\displaystyle \prod r_i $$ subject to total cost $\leq C$.

• DP Solution: Similar to knapsack but multiplicative reliability.

• Recurrence: $$\displaystyle R[i][c] = \max_{d \in \text{devices}_i} \{ r_d \times R[i-1][c - \text{cost}_d] \} $$.

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

  • Stage1: only device1 (cost30, r0.9) fits.

  • Stage2: with remaining 75, max r from stage2 devices (cost15,r0.8) → r=0.8.

  • Stage3: with remaining 60, max r from stage3 devices (cost20,r0.5) → r=0.5.

  • Total reliability = 0.9 × 0.8 × 0.5 = 0.36. (But need to explore all device combinations per stage for true optimum).

6. Backtracking

Concept & State-Space Tree

• Idea: Systematically explore all candidate solutions via depth-first search of state-space tree.

• Prune branches that cannot lead to a solution (using constraint functions).

• State-Space Tree: Nodes represent partial solutions; edges represent choices.

n-Queen Problem

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

• Algorithm (row-wise placement):

  
  PlaceQueen(row):
  
    if row > n: print solution; return
  
    for col=1 to n:
  
      if Safe(row, col):  // check column & diagonals
  
        place queen at (row,col)
  
        PlaceQueen(row+1)
  
        remove queen (backtrack)
  
  

• State-Space Tree for 4-Queen:

  DiagramCANVAS: Tree with root (row1). Branches: col1, col2, col3, col4. Safe placements only. Solutions: (2,4,1,3) and (3,1,4,2).

Subset Sum Problem

• Given: Set $$\displaystyle S=\{s_1,...,s_n\} $$, target $X$. Find subset summing to $X$.

• Backtracking (include/exclude):

  
  SubsetSum(i, current_sum):
  
    if current_sum == X: found solution
  
    if i>n or current_sum > X: return
  
    SubsetSum(i+1, current_sum + s_i)  // include s_i
  
    SubsetSum(i+1, current_sum)        // exclude s_i
  
  

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

  • Path: include1(1) → include3(4) → include4(8) → solution {1,3,4}.

  • Backtrack: exclude4(4) → include5(9) >8 prune → backtrack.

Graph Coloring (m-coloring)

• Color graph vertices with $m$ colors so no adjacent vertices same color.

• Algorithm: Assign colors to vertices sequentially; backtrack if conflict.

• Example: Triangle graph, $$\displaystyle m=2 $$ → impossible (backtrack all ways).

Hamiltonian Cycle

• Cycle visiting each vertex exactly once (return to start).

• Backtracking: Build path vertex by vertex; check if next vertex is unvisited and connected to current. If path length $n$ and last vertex connects to start → cycle found.

7. Branch and Bound

Concept & Reduction Method

• Idea: Systematically enumerate candidate solutions but prune branches using bounds (upper/lower) on best possible solution in that branch.

• Reduction: Transform problem into cost matrix; apply row/column reductions (subtract min) to get bound.

Traveling Salesman Problem (TSP)

• Branch and Bound Exact:

  1. Start with cost matrix, reduce rows/cols → get initial bound.

  2. For each edge $(i,j)$, create child node by forcing $i\to j$, setting row $i$, col $j$ to ∞, reducing matrix, adding cost $$\displaystyle c_{ij} $$ to bound.

  3. Use priority queue (min-heap) to explore node with lowest bound first.

  4. If bound $\geq$ best solution found → prune.

• Nearest Neighbor Approximation:

  1. Start at arbitrary city.

  2. Repeatedly go to nearest unvisited city.

  3. Return to start.

  • Accuracy Ratio: $$\displaystyle \frac{\text{Approx Cost}}{\text{Optimal Cost}} \leq \frac{\lceil \log_2 n \rceil + 1}{2} $$ for metric TSP.

• Example Cost Matrix:

  DiagramCANVAS: 5x5 matrix with ∞ diagonal. Apply reduction, branch on edges, find optimal tour cost.

8. Graph Traversals & Applications

Breadth-First Search (BFS)

• Queue-based. Visits vertices in increasing distance from start.

• Applications: Shortest path (unweighted), connected components, level order.

Depth-First Search (DFS)

• Stack-based (recursive or iterative). Explores as deep as possible.

• Applications: Topological sort, cycle detection, connected components, maze solving.

Comparison: BFS vs DFS

Topological Sorting

• Linear ordering of DAG vertices such that for every edge $(u,v)$, $u$ comes before $v$.

• Using DFS: Perform DFS, output vertices in reverse postorder (decreasing finish times).

• Example: Graph A→B, A→C, B→D, C→D. Topo order: A, B, C, D or A, C, B, D.

9. Advanced Data Structures

Binary Tree Traversals

• Preorder: Root → Left → Right.

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

• Postorder: Left → Right → Root.

Construct Tree from Traversals

• Inorder + Preorder: First in preorder = root. Find root in inorder → left/right subtrees. Recurse.

• Inorder + Postorder: Last in postorder = root.

• Example: 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 A → left subtree; right: E G D H F I J.

  • Preorder left: B C → root=B, etc.

    DiagramCANVAS: Tree constructed.

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

Binary Search Tree (BST)

• Operations: Insert, Search, Delete (standard BST delete: if node has two children, replace with inorder successor/predecessor, then delete that node).

• Example: Insert 20,49,41,93,69,90,76,62,81,75,10,79,87,38. Delete 41 (has two children: successor=49? Actually 41's successor is 62? Recheck tree structure). Delete 76 (has one child 75?).

AVL Trees

• Self-balancing BST. Height difference (Balance Factor) of left/right subtrees ≤ 1.

• Rotations:

  • Right Rotate (LL): Unbalanced at node with left-left heavy.

  • Left Rotate (RR): Unbalanced at node with right-right heavy.

  • Left-Right (LR): Left child right-heavy → rotate left on child, then right on node.

  • Right-Left (RL): Right child left-heavy → rotate right on child, then left on node.

• Insertion/Deletion: Perform standard BST op, then check balance up the path, apply rotations.

B-Trees (Order $m$)

• Properties:

  • Each node has max $m-1$ keys, min $\lceil m/2 \rceil -1$ keys (except root).

  • Keys in node are sorted; $k$ keys → $k+1$ children.

  • All leaves at same depth.

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

• Insertion:

  1. Search leaf where key belongs.

  2. Insert key. If overflow ($\geq m$ keys), split node: median moves up.

• Deletion Cases:

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

  2. Key in internal node: Replace with predecessor/successor (from leaf), then delete that leaf key.

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

  DiagramCANVAS: Show split operations.

2-3 Trees

• Special B-tree with $$\displaystyle m=3 $$:

  • 2-node: 1 key, 2 children.

  • 3-node: 2 keys, 3 children.

• Insertion: Insert in leaf; if 3-node becomes 4-node (overflow), split middle key up.

• Deletion: Similar to B-tree; merge underflow nodes.

Binomial Heaps

• Structure: Collection of binomial trees (like B-tree but different rules) following binary representation of $n$.

  • Binomial tree $$\displaystyle B_k $$: root degree $k$, children are $$\displaystyle B_{k-1},...,B_0 $$.

  • Heap property: keys in min-heap order within each tree.

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

• Operations:

  • Union (Meld): Merge two heaps by merging binomial trees by degree (like binary addition). $O(\log n)$.

  • Find Minimum: Traverse roots of all trees ($O(\log n)$).

  • Extract Min: Find min root, remove it, reverse its children into new heap, union with original. $O(\log n)$.

• Example: Union of heap with trees $$\displaystyle B_0, B_2, B_3 $$ and heap with $$\displaystyle B_1, B_2, B_3 $$. Merge like binary: $$\displaystyle B_0+B_1=B_1 $$, $$\displaystyle B_2+B_2=B_3 $$, $$\displaystyle B_3+B_3=B_4 $$, carry over. Result: $$\displaystyle B_1, B_4 $$.

10. Complexity Theory

Classes: P, NP, NP-Hard, NP-Complete

Relationships

P ⊆ NP ⊆ NP-Hard.

NP-Complete = NP ∩ NP-Hard.

$\boxed{\text{P} \subseteq \text{NP}}$ (trivial: if solvable in poly-time, verifiable in poly-time).

Whether $$\displaystyle \text{P} = \text{NP} $$ is unsolved.

Reductions to Prove NP-Completeness

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

2. Take known NP-Complete problem $L'$.

3. Construct polynomial-time reduction $f$ from $L'$ to $L$: $x \in L' \iff f(x) \in L$.

4. Conclude $L$ is NP-Hard. Since $L \in \text{NP}$, $L$ is NP-Complete.

11. Specialized Topics (Brief)

Parallel Algorithms

• Design: Partition work across processors; minimize communication.

• Complexity Measures: Work ($$\displaystyle T_1 $$), Span ($$\displaystyle T_\infty $$, longest path in dependency graph), Parallel Time ($$\displaystyle T_p $$ on $p$ processors).

• Speedup: $$\displaystyle S_p = T_1 / T_p $$. Linear speedup if $$\displaystyle S_p = \Theta(p) $$.

• Work-Efficient: $$\displaystyle T_p = \Theta(T_1 / p + T_\infty) $$.

Data Stream Algorithms

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

• Goal: Compute approximate summaries (counts, quantiles, heavy hitters).

• Examples: Misra-Gries (frequent items), Bloom filters (set membership), Count-Min Sketch (frequency estimation).

Approximation Algorithms

• For NP-Hard optimization problems. Compute solution fast with guaranteed worst-case performance.

• Performance Ratio (ρ): $$\displaystyle \frac{\text{Approx Cost}}{\text{Opt Cost}} \leq \rho $$ (minimization) or $\geq 1/\rho$ (maximization).

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

Data Transfer Optimization

• Problems: Minimize time/communication in distributed systems, network flow, file distribution.

• Algorithms: Multi-commodity flow, broadcast trees, peer-to-peer scheduling.

Logic Optimization

• Goal: Minimize Boolean function (gate count, delay).

• Techniques: Karnaugh Maps (up to 4 vars), Quine-McCluskey (tabulation), Espresso (heuristic), Binary Decision Diagrams (BDDs).

• Example: Simplify $$\displaystyle f(A,B,C,D) = \sum m(0,2,5,7,8,10,13,15) $$ using K-map → $$\displaystyle f = B'D' + BD $$.

Final Exam Strategy:

1. Identify paradigm from question (e.g., "greedy" → think MST, knapsack, Huffman).

2. State properties (greedy choice, optimal substructure, overlapping subproblems).

3. Write algorithm (pseudocode) clearly.

4. Trace example (use given data).

5. Analyze complexity (recurrence → Master Theorem if applicable).

6. Box final answer (time complexity, optimal value).