Design& Analysis of Algorithms (CY-502) - Unit 3 Short Notes

UNIT 3: Design & Analysis of Algorithms

I. FUNDAMENTALS OF ALGORITHM ANALYSIS

Time Complexity & Asymptotic Notations

• Definition: Time complexity $T(n)$ quantifies the amount of time an algorithm takes as a function of input size $n$. It is measured by counting elementary operations.

• Asymptotic Notations:

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

  • Big-Theta (Θ): $$\displaystyle f(n) = \Theta(g(n)) $$ if $\exists$ constants $$\displaystyle c_1, c_2 > 0, n_0 \geq 1 $$ such that $$\displaystyle 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) $$ for all $$\displaystyle n \geq n_0 $$. Tight bound.

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

  • little-o (o): $$\displaystyle f(n) = o(g(n)) $$ if $$\displaystyle \forall c > 0, \exists n_0 \geq 1 $$ such that $$\displaystyle 0 \leq f(n) < c \cdot g(n) $$ for all $$\displaystyle n \geq n_0 $$. Strictly smaller upper bound.

  • little-omega (ω): $$\displaystyle f(n) = \omega(g(n)) $$ if $$\displaystyle \forall c > 0, \exists n_0 \geq 1 $$ such that $$\displaystyle 0 \leq c \cdot g(n) < f(n) $$ for all $$\displaystyle n \geq n_0 $$. Strictly larger lower bound.

[!TIP] Common Pitfall: $O(g(n))$ is a set; we write $$\displaystyle f(n) = O(g(n)) $$ as shorthand for $f(n) \in O(g(n))$.

• Case Analysis:

  • Best-case: Minimum time over all inputs of size $n$ (e.g., already sorted array for some sorts).

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

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

• Proof Example: Prove $$\displaystyle f(n) = 5n^2 + 6n + 4 $$ is $$\displaystyle O(n^2) $$.

  For $n \geq 1$, $$\displaystyle 5n^2 + 6n + 4 \leq 5n^2 + 6n^2 + 4n^2 = 15n^2 $$. Choose $$\displaystyle c = 15, n_0 = 1 $$. Hence, $$\displaystyle f(n) = O(n^2) $$.

Space Complexity

• Definition: Amount of memory an algorithm uses as a function of input size $n$. Includes:

  • Auxiliary Space: Extra/temporary space used (excluding input).

  • Total Space: Input space + Auxiliary space.

• Analysis: Count memory for variables, data structures (arrays, matrices), and recursion stack space.

Recurrence Relations

• Writing Recurrences: For divide-and-conquer algorithms: $$\displaystyle T(n) = a \cdot T(n/b) + f(n) $$, where:

  • $a$ = number of subproblems.

  • $n/b$ = size of each subproblem.

  • $f(n)$ = cost of dividing/combining.

• Solving Recurrences:

  1. Substitution Method: Guess a bound, prove by induction.

  2. Recursion Tree Method: Visualize costs per level, sum them.

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

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

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

     • 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)) $$.

• High-Frequency Examples:

  • Binary Search: $$\displaystyle T(n) = T(n/2) + \Theta(1) $$. Solution: $$\displaystyle T(n) = \Theta(\log n) $$. Average-case also $\Theta(\log n)$.

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

  • Quick Sort (Average): $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) $$. Solution: $$\displaystyle T(n) = \Theta(n \log n) $$.

  • Strassen's: $$\displaystyle T(n) = 7T(n/2) + \Theta(n^2) $$. Master Theorem: $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}) $$.

II. ALGORITHM DESIGN PARADIGMS

A. Greedy Algorithms

• General Method: Makes locally optimal choice at each step with hope of finding global optimum.

• Characteristics for Correctness:

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

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

• Key Applications:

  • Fractional Knapsack:

    • Compute profit/weight ratio for each item.

    • Sort items by ratio in descending order.

    • Take items in order until knapsack is full (can take fraction of last item).

    • Time: $O(n \log n)$ for sorting.

  • 0/1 Knapsack: Greedy fails (cannot take fractions). Requires DP.

  • Job Sequencing with Deadlines:

    1. Sort jobs by profit descending.

    2. Initialize a slot array of size max deadline.

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

    4. Time: $$\displaystyle O(n^2) $$ or $O(n \log n)$ with Disjoint Set Union.

    [!TIP] Example (Dec 2024): $$\displaystyle n=6, p=(200,180,190,300,120,100), d=(5,3,2,4,2,4) $$. Sorted by profit: J4(300,d4), J1(200,d5), J3(190,d2), J2(180,d3), J5(120,d2), J6(100,d4). Schedule: Slot4=J4, Slot5=J1, Slot3=J2, Slot2=J3. Max Profit = 200+300+180+190 = 870.

  • Optimal Merge Pattern / Huffman Coding:

    • Goal: Merge $n$ sorted files with given sizes into one file with minimum total merge cost (cost = sum of sizes merged).

    • Greedy Strategy: Always merge the two smallest available files.

    • Huffman Coding: Builds a prefix-free binary code by:

      1. Create min-heap of leaf nodes (symbols with frequencies).

      2. Extract two nodes with smallest freq, create new internal node with freq = sum.

      3. Repeat until one node remains (root of Huffman tree).

    • Time: $O(n \log n)$ using heap.

  • Minimum Cost Spanning Tree (MCST):

    • Prim's Algorithm:

      • Start with an arbitrary vertex.

      • Grow tree by adding the minimum-weight edge connecting tree to a vertex outside.

      • Implementation: Use adjacency matrix ($$\displaystyle O(V^2) $$) or min-heap ($O(E \log V)$).

    • Kruskal's Algorithm:

      • Sort all edges by weight.

      • Add edges in order, skipping those that form a cycle (use Union-Find).

      • Time: $O(E \log E)$ or $O(E \log V)$ with optimized Union-Find.

B. Dynamic Programming (DP)

• General Method: Solves problems by combining solutions to overlapping subproblems. Stores results in a table (tabulation) or cache (memoization) to avoid recomputation.

• Characteristics vs D&C:

  | Feature | Divide & Conquer | Dynamic Programming | | :--- | :--- | :--- | | Subproblems | Non-overlapping | Overlapping | | Approach | Top-down (recursive) | Bottom-up (iterative) or Top-down with memoization | | Efficiency | Can be inefficient due to repeated work | Efficient, polynomial time | | Example | Merge Sort, Quick Sort | 0/1 Knapsack, Floyd-Warshall |

• Key Applications:

  • 0/1 Knapsack:

    • DP Table: $dp[i][w]$ = max 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}$$

    *   **Time & Space:** $O(nW)$ (pseudo-polynomial).

    > [!TIP] **Example (Nov 2022):** $$\displaystyle n=3, m=6, p=(1,2,5), w=(2,3,4) $$. Table yields max profit = **6** (items 2 & 3).

*   **Multistage Graph Problem:**

    *   **Definition:** Directed acyclic graph with stages; find shortest path from start (stage 1) to end (stage k).

    *   **DP Approach (Forward):**

        Let $$\displaystyle d_i(v) $$ = shortest distance from vertex $v$ in stage $i$ to terminal vertex.

        Recurrence: $$\displaystyle d_i(v) = \min_{w \in \text{Adj}(v)} \{ \text{cost}(v,w) + d_{i+1}(w) \} $$.

        Compute from last stage backward to first.

    *   **Time Complexity:** $O(V + E)$.

*   **All-Pairs Shortest Paths: Floyd-Warshall:**

    *   **Algorithm:** $$\displaystyle dist[i][j]^{(k)} $$ = shortest path from $i$ to $j$ using vertices $\{1..k\}$ as intermediates.

    *   **Recurrence:** $$\displaystyle dist[i][j]^{(k)} = \min(dist[i][j]^{(k-1)},\ dist[i][k]^{(k-1)} + dist[k][j]^{(k-1)}) $$.

    *   **In-place:** Use single $n \times n$ matrix, update iteratively for $$\displaystyle k=1 $$ to $n$.

    *   **Time:** $$\displaystyle O(n^3) $$. Handles negative edges (no negative cycles).

*   **Optimal Binary Search Trees (OBST):** Minimize expected search cost given access probabilities. DP table $e[i,j]$ for expected cost of subtree containing keys $$\displaystyle k_i..k_j $$.

C. Divide and Conquer (D&C)

• General Method:

  1. Divide: Split problem into smaller subproblems.

  2. Conquer: Solve subproblems recursively.

  3. Combine: Merge subproblem solutions.

• Recurrence: $$\displaystyle T(n) = aT(n/b) + f(n) $$.

• Key Algorithms:

  • Merge Sort:

    • Split array into halves, sort each recursively, merge two sorted halves.

    • Merge: $O(n)$.

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

  • Quick Sort:

    • Partition (Lomuto): Choose pivot (often last element). Rearrange so elements $$\displaystyle < pivot $$ left, $$\displaystyle > pivot $$ right. Return pivot index.

    • Partition (Hoare): Two pointers from ends, swap misplaced elements, return when cross.

    • Recurrence (Average): $$\displaystyle T(n) = \frac{2}{n} \sum_{k=0}^{n-1} T(k) + \Theta(n) \Rightarrow T(n) = \Theta(n \log n) $$.

    • Recurrence (Worst, already sorted): $$\displaystyle T(n) = T(n-1) + \Theta(n) \Rightarrow T(n) = \Theta(n^2) $$.

    [!TIP] Example (Dec 2024): Sort $$\displaystyle A = \{6, 15, 3, 14, 25, 36, 18\} $$ using Quick Sort (Lomuto, pivot=last). First partition around 18: $\{6,15,3,14,18,25,36\}$. Recurse on left $\{6,15,3,14\}$ and right $\{25,36\}$.

  • Binary Search: $$\displaystyle T(n) = T(n/2) + \Theta(1) \Rightarrow T(n) = \Theta(\log n) $$. Average-case same as worst-case.

  • Strassen's Matrix Multiplication:

    • Standard: 8 multiplications of $n/2 \times n/2$ matrices.

    • Strassen: Uses 7 multiplications via clever linear combinations.

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

    • Solution (Master Theorem): $$\displaystyle T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807}) $$.

    [!TIP] Example (Nov 2022): Multiply two $2 \times 2$ matrices using Strassen's 7 products.

III. BACKTRACKING & BRANCH & BOUND

A. Backtracking

• General Method: Systematic way to try all possible configurations (state-space tree). Abandon a branch ("backtrack") as soon as it is determined that it cannot lead to a valid solution.

• Key Problems:

  • n-Queens Problem: Place $n$ queens on $n \times n$ chessboard so no two attack.

    • Algorithm: Place queens row by row. For each row, try each column. Check if safe (no conflict with previously placed queens in columns or diagonals). If safe, place and recurse for next row. If no column works, backtrack.

    • State-space tree for 4-Queens: Depth 4, branching factor up to 4. Solutions: [2,4,1,3] and [3,1,4,2] (1-indexed columns).

  • Graph Coloring (m-coloring):

    • Algorithm: Assign colors to vertices sequentially. For vertex $v$, try colors $1..m$. If a color $c$ is not used by any adjacent colored vertex, assign $c$ and recurse for next vertex. Else try next color. If no color works, backtrack.

    • Time: $$\displaystyle O(m^n) $$ worst-case.

  • Hamiltonian Cycle: Find a cycle visiting each vertex exactly once.

    • Algorithm: Start from vertex 0. Build path by adding vertices one by one. Check if next vertex is adjacent to last in path and not already in path. If path length = $n$ and last vertex adjacent to start, cycle found.

B. Branch and Bound (B&B)

• General Method: Systematically enumerate candidate solutions by state-space tree, but prune branches that cannot yield a better solution than the best found so far.

• Node Types:

  • Live Node: Generated but not fully explored.

  • E-node (Expanding Node): Live node being explored.

  • Dead Node: Pruned or fully explored.

• Cost Function: Assigns a bound to each node. For minimization, if bound $\geq$ best solution cost, prune.

• Key Application: Traveling Salesperson Problem (TSP)

  1. Reduction (Cost Matrix): For each row, subtract row min. For each col, subtract col min. Lower bound = sum of all subtractions.

  2. State-space tree: Each level $i$ represents choosing the $i$-th city after start.

  3. Lower Bound for child node (from node $u$ to $v$): $$\displaystyle LB(v) = LB(u) + \text{cost}[u][v] + \text{row/col reduction cost for new matrix} $$ (where row of $u$ and col of $v$ are made $\infty$).

  4. Use priority queue (min-heap) to expand node with smallest lower bound first.

• Comparison with Backtracking:

  | Feature | Backtracking | Branch and Bound | | :--- | :--- | :--- | | Purpose | Decision problems (is there a solution?) | Optimization problems (find best solution) | | Pruning | Based on feasibility constraints | Based on bound vs. current best | | Exploration | Depth-first typically | Can be best-first (using priority queue) |

IV. COMPLEXITY THEORY & NP-CLASSES

• P: Class of decision problems solvable in polynomial time by a deterministic Turing machine. (e.g., sorting, shortest path).

• NP: Class of decision problems for which a "yes" instance can be verified in polynomial time given a certificate (proof). Equivalently, solvable in polynomial time by a non-deterministic Turing machine.

  • All problems in P are in NP ($P \subseteq NP$).

• NP-Hard: Problems to which every problem in NP can be reduced in polynomial time. Not necessarily in NP (may be optimization or undecidable). If any NP-Hard problem is in P, then P = NP.

• NP-Complete: Problems that are both NP-Hard and in NP. The "hardest" problems in NP.

• Reduction: To prove problem $A$ is NP-Hard, take a known NP-Complete problem $B$ and show $$\displaystyle B \leq_p A $$ (polynomial-time transformation from instances of $B$ to $A$).

• Comparison:

  | Class | In NP? | NP-Hard? | Example | | :--- | :--- | :--- | :--- | | P | Yes | No | Sorting, MST | | NP-Complete | Yes | Yes | SAT, 0/1 Knapsack (decision), Clique | | NP-Hard | No (usually) | Yes | TSP (optimization), Halting Problem | | Not in NP | No | No | Easy problems outside NP (rare) |

[!TIP] Mnemonic: NP-Complete = "NP" + "Complete" (hardest in NP). NP-Hard is at least as hard as NP-Complete.

• Lower Bound Theory:

  • Concept: A lower bound $\Omega(f(n))$ for a problem states that any algorithm solving it must take at least $c \cdot f(n)$ time for some constant $c$ and large $n$.

  • Comparison-based Sorting Lower Bound: Any comparison-based sorting algorithm requires $\Omega(n \log n)$ comparisons in the worst case. Proof via decision tree (leaf count $n!$, height $$\displaystyle \geq \log_2(n!) = \Omega(n \log n) $$).

V. SPECIALIZED ALGORITHMS & TOPICS

A. Graph & Tree Algorithms

• B-Trees (Order $m$):

  • Properties: Balanced search tree. Each node has $\lceil m/2 \rceil$ to $m$ children (except root). All leaves at same depth.

  • Insertion: Insert key in leaf; if leaf overflows ($$\displaystyle > m-1 $$ keys), split median to parent.

  • Search: $$\displaystyle O(\log_m n) $$ I/O operations; ideal for disk-based systems (minimize seeks).

  • Advantages: Reduces height, keeps data sorted, efficient for block access.

• Floyd-Warshall Algorithm: (See DP section above).

B. Polynomial & Number Theoretic

• Horner's Algorithm (Polynomial Evaluation):

  • Evaluate $$\displaystyle p(x) = a_0 + a_1x + a_2x^2 + ... + a_nx^n $$.

  • Method: $$\displaystyle p = a_n $$; for $$\displaystyle i = n-1 $$ downto 0: $$\displaystyle p = p \cdot x + a_i $$.

  • Time: $O(n)$ multiplications/additions.

  • Example: $$\displaystyle p(x)=2+3x+5x^2 $$ at $$\displaystyle x=2 $$: $$\displaystyle p=5 $$; $$\displaystyle p=5*2+3=13 $$; $$\displaystyle p=13*2+2=28 $$.

C. Miscellaneous / Short Notes

• Parallel Algorithms:

  • Concept: Use multiple processors/computers simultaneously to speed up computation.

  • Models: PRAM (Parallel Random Access Machine) - shared memory, variants (CREW, CRCW).

  • Speedup: $$\displaystyle S(p) = T_{seq}/T_{par}(p) $$. Ideal: linear speedup $$\displaystyle S(p)=p $$.

  • Example: Parallel Merge Sort (divide in parallel, merge sequentially).

• Data Stream Algorithms:

  • Context: Massive data streams (network traffic, sensor data) where data cannot be stored.

  • Goal: Compute summaries (distinct elements, heavy hitters, quantiles) using limited memory (sublinear in stream length).

  • Examples:

    • Counting Distinct Elements: Flajolet-Martin algorithm (bit patterns, stochastic averaging).

    • Heavy Hitters (Frequent Items): Misra-Gries algorithm (keep $k-1$ candidate items with counts).

• Logic Optimization:

  • Goal: Simplify Boolean functions (minimize gates/cost in circuits).

  • Methods:

    • Karnaugh Map (K-map): Graphical method for up to 4-6 variables. Group adjacent 1s (implicants) to find prime implicants and essential primes.

    • Quine-McCluskey: Tabular method for many variables. Find prime implicants, then minimal cover via Petrick's method.

  • Relevance: Reduces hardware cost, power consumption, increases speed.

• Optimal Merge Pattern: (See Greedy/Huffman). Theory: Merging sorted files of sizes $$\displaystyle s_1, s_2, ..., s_n $$ with cost $$\displaystyle s_i + s_j $$ per merge. Greedy (merge smallest first) yields minimum total cost. Equivalent to constructing Huffman tree.

VI. SYNTHESIS & COMPARISON QUESTIONS

Differentiate between:

General Method Summaries:

• Greedy: Sort/select by a criterion, take locally best, hope for global.

• Dynamic Programming: Characterize optimal substructure, define recursive relation, fill table bottom-up.

• Branch and Bound: Use cost function to bound, expand most promising node (min bound for minimization), prune when bound $\geq$ incumbent.

• Backtracking: Build solution incrementally, check constraints at each step, backtrack on failure.

\boxed{\text{End of Unit 3 Notes}}