UNIT 4: Analysis and Design of Algorithm – Short Notes

I. Fundamentals of Algorithm Analysis

Asymptotic Notations

Definitions:

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

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

• Big Theta (Tight Bound): $$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$.

Significance:

• O: Describes worst-case growth rate.

• Ω: Describes best-case growth rate.

• Θ: Describes exact asymptotic growth.

Examples (from Jun 2022):

1. $$\displaystyle f(n) = \frac{n(n-1)}{2} = \Theta(n^2) $$

2. $$\displaystyle f(n) = 6 \cdot 2^n + n^2 = \Theta(2^n) $$

3. $$\displaystyle f(n) = 100n + 7 = \Theta(n) $$

[!TIP]

Common Pitfall: Confusing $O$ with $\Theta$. Always prove both upper and lower bounds for $\Theta$.

Recurrence Relations

Solving Techniques:

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

2. Recursion Tree: Visualize cost at each level, sum costs.

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

   • If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$, 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}) $$, then $$\displaystyle T(n) = \Theta(f(n)) $$.

From Recursive Algorithms:

• Binary Search: $$\displaystyle T(n) = T(n/2) + O(1) $$ → $$\displaystyle T(n) = O(\log n) $$.

• Merge Sort: $$\displaystyle T(n) = 2T(n/2) + O(n) $$ → $$\displaystyle T(n) = O(n \log n) $$.

Complex Recurrence (Jun 2025):
$$\displaystyle T(n)=n+T\left(\frac{n}{10}\right)+T\left(\frac{7n}{5}\right) $$

[!TIP]

Solution Sketch: Recursion tree shows dominant term from $T(7n/5)$ → $$\displaystyle T(n) = \Theta(n^{\log_{5/7} 2}) $$? Actually, check: $$\displaystyle a_1=1, b_1=10; a_2=1, b_2=5/7 $$. Total work per level grows → $$\displaystyle T(n) = \Theta(n^{\log_{5/7} 2}) $$? Wait, better use Akra-Bazzi method. For $$\displaystyle T(n) = \sum_{i=1}^k a_i T(n/b_i) + g(n) $$, find $p$ such that $$\displaystyle \sum a_i b_i^p = 1 $$. Here: $$\displaystyle 1 \cdot (1/10)^p + 1 \cdot (5/7)^p = 1 $$. Solve numerically: $p \approx 1.19$. Then $$\displaystyle T(n) = \Theta(n^p (1 + \int_1^n g(u)/u^{p+1} du)) $$. With $$\displaystyle g(n)=n $$, integral $\sim \log n$ → $$\displaystyle T(n) = \Theta(n^{1.19} \log n) $$.

Time Complexity Cases

• Worst-case: Maximum time over all inputs (e.g., Quick Sort $$\displaystyle O(n^2) $$). Relevance: Real-time systems, guarantees.

• Average-case: Expected time over random inputs (e.g., Quick Sort $O(n \log n)$). Relevance: Probabilistic analysis.

• Best-case: Minimum time (e.g., already sorted array for some algorithms). Relevance: Optimistic scenarios.

[!TIP]

Exam Focus: Worst-case is most commonly asked. Know when average-case is used (e.g., randomized Quick Sort).

Algorithm Design Process

1. Problem Definition: Formal specification.

2. Design: Choose paradigm (divide & conquer, greedy, etc.).

3. Analysis: Time/space complexity.

4. Implementation: Coding.

5. Testing: Validation.

Trade-offs:

• Readability vs Optimization: Optimize only after profiling.

• Maintainability vs Performance: Prefer clear code unless critical.

[!TIP]

Flow Chart: Not typically asked, but know steps.

II. Divide and Conquer

General Method

Steps:

1. Divide: Split problem into subproblems.

2. Conquer: Solve subproblems recursively.

3. Combine: Merge solutions.

Recurrence: $$\displaystyle T(n) = aT(n/b) + f(n) $$, where $a$ = subproblems, $n/b$ = size, $f(n)$ = combine cost.

Binary Search

Algorithm (Recursive):

BinarySearch(A, low, high, key):

    if low > high: return -1

    mid = (low + high)/2

    if A[mid] == key: return mid

    if A[mid] > key: return BinarySearch(A, low, mid-1, key)

    else: return BinarySearch(A, mid+1, high, key)

Recurrence: $$\displaystyle T(n) = T(n/2) + O(1) $$
Complexity: $O(\log n)$.

Maximum and Minimum Elements

Divide & Conquer Approach:

• Split array into halves.

• Find max/min in each half recursively.

• Compare two maxima and two minima → 2 comparisons per level.

Recurrence: $$\displaystyle T(n) = 2T(n/2) + 2 $$
Complexity: $O(n)$ (better than naive $2n-2$ comparisons? Actually naive is $2n-2$, this is $\approx 1.5n$ comparisons for $$\displaystyle n>1 $$).
Example (Jun 2022): For [65,70,75,80,85,60,55,50], pairs: (65,70)→max70 min65; (75,80)→max80 min75; (85,60)→max85 min60; (55,50)→max55 min50. Then compare maxes: 80 vs 85 →85; mins: 65 vs 50 →50. Total comparisons: 4*2 + 2 + 2 = 12? Actually standard: for n=8, comparisons = 8 + (8/2 - 1)*2 = 8 + 7 = 15? Wait, formula: $$\displaystyle C(n) = 2n - 2 $$ for naive; divide & conquer: $$\displaystyle C(n) = 2C(n/2) + 2 $$, $$\displaystyle C(2)=1 $$, so $$\displaystyle C(8)=2*C(4)+2=2*(2*C(2)+2)+2=2*(2*1+2)+2=2*4+2=10 $$. Yes, 10 comparisons vs 14 for naive.

Merge Sort

Algorithm:

MergeSort(A, l, r):

    if l < r:

        mid = (l+r)/2

        MergeSort(A, l, mid)

        MergeSort(A, mid+1, r)

        Merge(A, l, mid, r)

Merge(A, l, mid, r):

    create temp arrays L[0..mid-l], R[0..r-mid]

    copy data to L, R

    i=j=0, k=l

    while i<len(L) and j<len(R):

        if L[i] <= R[j]: A[k]=L[i]; i++

        else: A[k]=R[j]; j++

        k++

    copy remaining L or R

Complexity: $O(n \log n)$ in all cases (worst, average, best).
Example (Jun 2023): Sort {23, 11, 5, 15, 68, 31, 4, 17}.

Step-by-step: Split recursively → merge sorted halves.

Quick Sort

Algorithm:

QuickSort(A, low, high):

    if low < high:

        pi = Partition(A, low, high)

        QuickSort(A, low, pi-1)

        QuickSort(A, pi+1, high)

Partition(A, low, high):

    pivot = A[high]  // or other pivot selection

    i = low-1

    for j=low to high-1:

        if A[j] <= pivot:

            i++

            swap A[i] and A[j]

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

    return i+1

Average-case: $O(n \log n)$ (assuming random pivot).
Worst-case: $$\displaystyle O(n^2) $$ when array sorted or reverse sorted with poor pivot (e.g., last element).
Pivot Strategies: First, last, random, median-of-three.

Example (Jun 2023): Sort 20,35,10,16,54,21,25.

Pivot=25 (last). Partition: [20,10,16,21] [25] [35,54]. Recurse.

Strassen’s Matrix Multiplication

Algorithm (for 2x2):

Given matrices $A, B$:

• Compute 7 products:

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

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

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

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

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

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

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

• Combine:

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

Complexity:

Conventional: $$\displaystyle O(n^3) $$

Strassen’s: $$\displaystyle T(n) = 7T(n/2) + O(n^2) $$ → $$\displaystyle T(n) = O(n^{\log_2 7}) \approx O(n^{2.81}) $$.
Example (Jun 2022): Multiply $\begin{bmatrix}4 & 3\\2 & 1\end{bmatrix}$ and $\begin{bmatrix}2 & 5\\1 & 6\end{bmatrix}$.

Compute $$\displaystyle M_1 $$ to $$\displaystyle M_7 $$, then $$\displaystyle C_{11}, C_{12}, C_{21}, C_{22} $$.

[!TIP]

Why better? Reduces multiplications from 8 to 7 at cost of more additions. For large $n$, $$\displaystyle n^{2.81} < n^3 $$.

III. Greedy Algorithms

Greedy Choice Property & Optimal Substructure

• Greedy Choice Property: A global optimum can be reached by selecting a local optimum without reconsidering previous choices.

• Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems. Both required for correctness. (Jun 2024 asked importance).

Minimum Spanning Tree (MST)

Kruskal’s Algorithm:

1. Sort edges by weight (ascending).

2. Initialize forest (each vertex separate).

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

   • If u and v in different trees, add edge and merge trees (Union-Find).

4. Stop when n-1 edges added.

Union-Find: Find (with path compression) and Union (by rank).

Prim’s Algorithm:

1. Start with arbitrary vertex.

2. Grow tree: at each step, add minimum-weight edge connecting tree to outside vertex (priority queue).

3. Repeat until all vertices included.

Proof of Correctness: Cut Property: For any cut, lightest edge crossing cut is in some MST.
Uniqueness: With distinct weights, MST is unique (proof by cut property: any other MST would have heavier edge somewhere).
Example (Jun 2025): Asked to prove uniqueness with example.

Job Sequencing with Deadlines

Greedy Approach:

1. Sort jobs by profit descending.

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

3. For each job in sorted order:

   • Find latest available slot ≤ deadline (from right to left).

   • If found, schedule job there.

4. Scheduled jobs yield max profit.

Example (Jun 2024, Jun 2023):

n=4, profits=(100,10,15,27), deadlines=(2,1,2,1).

Sort by profit: Job1(100,d=2), Job4(27,d=1), Job3(15,d=2), Job2(10,d=1).

Slot for Job1: slot2. Job4: slot1. Job3: no slot (slot2 taken). Job2: no slot.
Optimal profit=127.

Fractional Knapsack Problem

Greedy by Profit/Weight Ratio:

1. Compute $$\displaystyle p_i/w_i $$ for each item.

2. Sort items by ratio descending.

3. Take items in order until knapsack full; if last item doesn’t fit, take fraction.

Example (Jun 2024, Dec 2024):

n=7, m=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,w=1), item6(4.5,w=4), item1(5,w=2), item7(3,w=1), item3(3,w=5), item2(1.67,w=3), item4(1,w=7).

Take item5 (w=1, profit=6, rem=14), item6 (w=4, profit=18, rem=10), item1 (w=2, profit=10, rem=8), item7 (w=1, profit=3, rem=7), item3 (w=5, profit=15, rem=2), then fraction of item2: 2/3 *5 = 3.33.
Total profit=6+18+10+3+15+3.33=55.33.

[!TIP]

Greedy vs DP: Fractional knapsack greedy works; 0/1 knapsack requires DP.

Huffman Coding

Tree Construction:

1. Create min-heap of nodes (character, frequency).

2. While heap size > 1:

   • Extract two smallest freq nodes.

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

   • Insert new node into heap.

3. Remaining node is root.

Optimality: Minimizes average code length $$\displaystyle \sum p_i l_i $$.
Average Code Length: $$\displaystyle L = \frac{\sum (freq_i \cdot depth_i)}{\sum freq_i} $$.

Example (Jun 2024):

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

Frequencies (assume total 100): 7,9,12,22,23,27.

Steps: Merge 7+9=16, heap: 12,16,22,23,27. Merge 12+16=28, heap: 22,23,27,28. Merge 22+23=45, heap: 27,28,45. Merge 27+28=55, heap: 45,55. Merge 45+55=100.

Tree: f(27) and e(23) under 50? Actually careful: last merges: 27+28=55 (node1), 45+55=100 (root). 28 from 12+16, 16 from 7+9. So codes: f:0, e:10, d:110, c:1110, b:11110, a:11111? Let's compute depths: f depth1, e depth2, d depth3, c depth4, b depth5, a depth5. Average length = 0.271 + 0.232 + 0.223 + 0.124 + 0.095 + 0.075 = 0.27+0.46+0.66+0.48+0.45+0.35 = 2.67 bits/char.

Optimal Merge Patterns

Problem: Merge sorted files with minimal total comparisons (or cost proportional to size).
Greedy: Always merge two smallest files first (like Huffman).
Example (Jun 2023): Files sizes: 10, 20, 30, 40.

Merge 10+20=30 (cost30), files: 30,30,40. Merge 30+30=60 (cost60), files: 60,40. Merge 60+40=100 (cost100). Total cost=30+60+100=190.

Single Source Shortest Path (Dijkstra)

Algorithm (non-negative weights):

1. Initialize dist[v]=∞ for all v, dist[source]=0. Priority queue Q with all vertices keyed by dist.

2. While Q not empty:

   • Extract u with min dist.

   • For each neighbor v of u:

     • If dist[u] + w(u,v) < dist[v]: update dist[v] and predecessor.

Example (Jun 2024): Apply on given graph (not provided here).

[!TIP]

Dijkstra vs Bellman-Ford: Dijkstra requires non-negative weights; Bellman-Ford handles negatives but $O(VE)$.

IV. Dynamic Programming

Principle

• Overlapping Subproblems: Same subproblems solved repeatedly → store solutions (memoization/tabulation).

• Optimal Substructure: Global optimum from optimum of subproblems.

• Memoization: Top-down (recursive with cache).

• Tabulation: Bottom-up (fill table iteratively).

0/1 Knapsack Problem

Problem: n items, profit $$\displaystyle p_i $$, weight $$\displaystyle w_i $$, capacity $W$. Choose subset with total weight ≤ $W$ maximizing profit. Each item taken or not.

DP Table (Tabulation):

Let $dp[i][w]$ = max profit using first $i$ items with capacity $w$.

for i=0 to n: dp[i][0] = 0

for w=0 to W: dp[0][w] = 0

for i=1 to n:

    for w=1 to W:

        if w_i <= w:

            dp[i][w] = max(dp[i-1][w], dp[i-1][w-w_i] + p_i)

        else:

            dp[i][w] = dp[i-1][w]

Complexity: $O(nW)$.

Example (Jun 2023):

P=(11,21,31,33), W=(2,12,23,15), C=42, n=4.

Table:

i\w: 0 1 2 ... 12 ... 23 ... 42

i=1 (w=2,p=11): w<2:0; w>=2: max(0, dp[0][w-2]+11)=11 for w>=2.

i=2 (w=12,p=21): for w>=12: max(dp[1][w], dp[1][w-12]+21). At w=12: max(11, dp[1][0]+21=21)=21.

i=3 (w=23,p=31): at w=23: max(dp[2][23]=21, dp[2][0]+31=31)=31.

i=4 (w=15,p=33): at w=42: max(dp[3][42]=31+? Actually need full table. At w=42: consider item4: dp[3][42-15=27] +33. dp[3][27]? From i=3, w=27: max(dp[2][27], dp[2][4]+31). dp[2][27]=21 (since only item2 fits? Actually item2 weight12, so dp[2][27]=max(dp[1][27]=11, dp[1][15]+21=11+21=32? Wait dp[1][15]=11, so 32). Then dp[3][27]=max(32, dp[2][4]+31=0+31=31)=32. Then dp[4][42]=max(dp[3][42], 32+33=65). dp[3][42]? From i=3, w=42: max(dp[2][42], dp[2][19]+31). dp[2][42]=? item2 weight12, so dp[2][42]=max(dp[1][42]=11, dp[1][30]+21=11+21=32)=32. dp[2][19]=max(dp[1][19]=11, dp[1][7]+21=11+21=32)=32. So dp[3][42]=max(32, 32+31=63)=63. Then dp[4][42]=max(63, 65)=65. Optimal profit=65 (items 2 and 4? weight12+15=27, profit21+33=54? Not 65. Actually items 1,3,4? weight2+23+15=40, profit11+31+33=75? But weight40≤42, profit75. But table gave 65? Mistake in calculation. Let's recalc properly:

Items:
1: w2 p11
2: w12 p21
3: w23 p31
4: w15 p33

Capacity 42.

Possible: items 1,2,4: w2+12+15=29, p11+21+33=65.

Items 1,3,4: w2+23+15=40, p11+31+33=75.

Items 2,3: w12+23=35, p21+31=52.

So max is 75.

DP table:

i=1: for w>=2: 11.

i=2: for w<12: dp[1][w]; for w>=12: max(dp[1][w], dp[1][w-12]+21). So at w=12: max(11,0+21)=21. At w=14: max(11, dp[1][2]+21=11+21=32)=32.

i=3: w=23: max(dp[2][23], dp[2][0]+31)=max(32,31)=32? Actually dp[2][23]: since w23>=12, max(dp[1][23]=11, dp[1][11]+21=11+21=32)=32. So dp[3][23]=max(32,31)=32. But we can take item3 alone:31, but 32>31. At w=25: max(dp[2][25]=32, dp[2][2]+31=11+31=42)=42. At w=40: dp[3][40]=max(dp[2][40]=? dp[2][40]=max(dp[1][40]=11, dp[1][28]+21=11+21=32)=32, dp[2][17]+31= dp[2][17]=max(dp[1][17]=11, dp[1][5]+21=11+21=32)=32, so 32+31=63). So dp[3][40]=63.

i=4: w=42: max(dp[3][42], dp[3][27]+33). dp[3][42]=? w42: max(dp[2][42]=32, dp[2][19]+31= dp[2][19]=max(dp[1][19]=11, dp[1][7]+21=11+21=32)=32, so 32+31=63) →63. dp[3][27]=? w27: max(dp[2][27]=32, dp[2][4]+31=0+31=31)=32. So dp[4][42]=max(63, 32+33=65)=65. But we expected 75. Where is 75? Items 1,3,4: weight2+23+15=40, profit11+31+33=75. That should be in dp[4][40]? dp[4][40]=max(dp[3][40]=63, dp[3][25]+33). dp[3][25]=? w25: max(dp[2][25]=32, dp[2][2]+31=11+31=42)=42. So dp[4][40]=max(63,42+33=75)=75. Then at w=42, we can also have 75? But dp[4][42] considers adding item4 to dp[3][27] (65) or not (63). But we can also have items 1,3,4 at weight40, which is ≤42, so dp[4][42] should be at least 75. Actually dp[i][w] is max profit for exactly capacity w? Usually it's for capacity ≤ w. So dp[4][42] should be max over all w'≤42. But our recurrence only considers exact w? Actually standard recurrence: dp[i][w] = max profit with capacity exactly w? No, it's with capacity at most w. But the recurrence as written gives max for capacity exactly w? Let's see: if we define dp[i][w] as max profit using first i items with total weight ≤ w, then recurrence is correct because we take max of not taking i (dp[i-1][w]) and taking i (dp[i-1][w-w_i]+p_i) only if w_i≤w. That gives max for weight ≤ w. So dp[4][42] should be max of all combinations with total weight ≤42. But our calculation for dp[4][42] only considered two cases: not taking item4 (dp[3][42]=63) and taking item4 with remaining capacity 27 (dp[3][27]+33=65). But what about taking items 1,3,4? That has weight40, which is ≤42, and profit75. That combination would be captured when taking item4 and using dp[3][25]? Because items 1 and 3 have total weight 2+23=25, profit11+31=42. Then adding item4 (w15) gives total weight40, profit42+33=75. But in dp[4][42], when taking item4, we look at dp[3][42-15=27]. But dp[3][27] is max profit with first 3 items and capacity ≤27. That includes items 1 and 3? Weight25≤27, profit42. So dp[3][27] should be 42, not 32. Let's recalc dp[3][27]:

i=3, w=27:

Option1: not take item3 → dp[2][27].

Option2: take item3 → if w23≤27, dp[2][27-23=4] +31.

dp[2][27]: from i=2, w=27: not take item2 → dp[1][27]=11; take item2 → dp[1][27-12=15]+21. dp[1][15]=11 (since item1 weight2, fits). So 11+21=32. So dp[2][27]=max(11,32)=32.

dp[2][4]: w4: not take item2 → dp[1][4]=11; take item2? w12>4, no. So dp[2][4]=11.

Thus dp[3][27]=max(32, 11+31=42)=42.

Then dp[4][42]=max(dp[3][42], dp[3][27]+33)=max(63, 42+33=75)=75.

So correct.
Final answer: 75.

All-Pairs Shortest Paths (Floyd-Warshall)

Algorithm:

for k=1 to n:

    for i=1 to n:

        for j=1 to n:

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

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

Complexity: $$\displaystyle O(n^3) $$.
Negative Cycle Detection: If dist[i][i] < 0 after algorithm, negative cycle exists.

Example (Jun 2024, Jun 2022): Apply on given graph (not provided).

Multistage Graph Problem

Problem: Directed acyclic graph with stages. Find shortest path from start to end. Forward Approach (Dynamic Programming):

Let $$\displaystyle f_i $$ = cost from stage i to end. $$\displaystyle f_n = 0 $$.

For i from n-1 down to 1: $$\displaystyle f_i = \min_{j \in \text{successors}(i)} \{ c(i,j) + f_j \} $$.

Example (Jun 2023): Given stages and costs, compute $$\displaystyle f_1 $$.

Computing Time: $$\displaystyle O(n^2) $$ if each vertex has at most n successors.

Reliability Design Problem

Problem: Design system with components in series/parallel to maximize reliability under cost constraint. Dynamic Programming:

Let $R[i][c]$ = max reliability for first i components with cost ≤ c.

Recurrence similar to knapsack but with reliability combination (series: product; parallel: 1 - product of failures).

Example (Jun 2023, Dec 2024):
3-stage system, devices d1(cost30,r0.9), d2(cost15,r0.8), d3(cost20,r0.5), total cost ≤105.

Typically, each stage chooses one device type (multiple copies allowed? Usually one per stage).

DP: stages 1,2,3. Cost constraint. For each stage, choose device type. Reliability multiplies across stages (series).

Maximize $$\displaystyle r_1 \cdot r_2 \cdot r_3 $$ subject to $$\displaystyle c_1+c_2+c_3 \leq 105 $$.

Try combinations:

(30,15,20)=65, reliability=0.90.80.5=0.36.

Can we use multiple of same? If allowed, use more reliable devices. But usually one per stage. So max reliability with cost ≤105: all three fit, so 0.36. But maybe we can use two of d1? But each stage only one device. So answer 0.36? But cost 65 <105, can we upgrade? No other devices. So 0.36.

If parallel allowed within stage, more complex. But question likely simple series with one device per stage.

Transitive Closure (Warshall’s Algorithm)

Derived from Floyd-Warshall: For reachability.

for k=1 to n:

    for i=1 to n:

        for j=1 to n:

            reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j])

Initialize: reach[i][j]=1 if edge (i,j) exists or i=j, else 0.

Example (Jun 2023): Generate transitive closure for given graph.

V. Backtracking

General Method

• State-space tree: Nodes represent partial solutions.

• Pruning: Abandon branch as soon as determined it cannot lead to solution.

• Recursive backtracking: Try each possibility, backtrack on failure. Use for: Constraint satisfaction problems (n-queen, subset sum, graph coloring).

n-Queen Problem

Problem: Place n queens on n×n chessboard so no two attack. Backtracking Algorithm:

PlaceQueens(row):

    if row > n: solution found

    else:

        for col=1 to n:

            if safe(row, col):

                place queen at (row,col)

                PlaceQueens(row+1)

                remove queen (backtrack)

Safe: Check column and diagonals for previous rows.

4-Queen Example (Jun 2022, Nov 2023):

State-space tree: root → row1 col1, then row2 col3? etc.

Solutions: [2,4,1,3] (row1 col2, row2 col4, row3 col1, row4 col3) and [3,1,4,2].

8-Queen (Jun 2023): Similar, more solutions.

Subset Sum Problem

Problem: Given set S and target X, find subset summing to X. Backtracking:

SubsetSum(index, current_sum):

    if current_sum == X: solution found

    if index > n or current_sum > X: return

    // include S[index]

    SubsetSum(index+1, current_sum + S[index])

    // exclude S[index]

    SubsetSum(index+1, current_sum)

Example (Jun 2025): S={1,3,4,5}, X=8.

State-space: include/exclude each. Solutions: {3,5}, {1,3,4}.

Hamiltonian Cycle Problem

Problem: Find cycle visiting each vertex exactly once. Backtracking:

Hamiltonian(v, count):

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

    else:

        for each neighbor u of v:

            if not visited[u]:

                visited[u]=true

                Hamiltonian(u, count+1)

                visited[u]=false

Example (Jun 2023, Jun 2022): Trace on given graph.

Graph Coloring (m-coloring)

Problem: Color graph with m colors so adjacent vertices different. Backtracking:

Color(v):

    if v > n: solution

    else:

        for c=1 to m:

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

                assign color c to v

                Color(v+1)

                remove color (backtrack)

Example (Jun 2023, Jun 2024): Given graph and m colors.

VI. Branch and Bound

General Method

• Bounding Function: Upper/lower bound on cost in subtree.

• Live Node: Node generated but not expanded.

• Best-First Search (LC-search): Expand live node with best bound. Control Abstraction:

Initialize live node list with root.

while list not empty:

    select node N with best bound

    if N is solution: update best, prune

    else: generate children, compute bounds, add to list

Traveling Salesman Problem (TSP)

Reduction Method:

1. Cost Matrix Reduction: For each row, subtract min; for each col, subtract min. Total reduction added to cost.

2. Branching: Choose edge (i,j). Create two branches:

   • Include (i,j): set row i and col j to ∞, set (j,i) to ∞ (avoid subtour), reduce matrix.

   • Exclude (i,j): set (i,j)=∞, reduce.

3. Bounding: Cost so far + reduced cost.

4. Select node with least bound.

Nearest Neighbor Approximation (Jun 2022):

• Start at arbitrary vertex.

• Repeatedly go to nearest unvisited neighbor.

• Return to start. Accuracy Ratio: $$\displaystyle \frac{\text{approx cost}}{\text{optimal cost}} $$. For metric TSP, ratio ≤ log n? Actually nearest neighbor can be bad. Typically ratio O(log n).

Example (Dec 2024): Given matrix, apply branch and bound (14m question).

0/1 Knapsack (Branch and Bound)

Bounding: Use fractional knapsack (greedy) on remaining items to get upper bound. State-space tree: Nodes represent items considered, with current weight and profit. Bound = current profit + fractional profit of remaining capacity. Branching: Include/exclude next item. Prune: If bound ≤ best profit so far.

VII. Advanced Data Structures

Binary Search Trees (BST)

Operations:

• Search: Recursive/iterative, $O(h)$.

• Insert: Search for null, insert as leaf.

• Delete: Three cases: leaf, one child, two children (replace with inorder successor/predecessor).

Construction from Traversals (Jun 2023):

Given inorder and preorder:

Inorder: B C A E G D H F I J

Preorder: A B C D E G F H I J

Root = first preorder = A.

In inorder, left of A: B C A? Actually inorder: B C A E G D H F I J → left subtree: B C, right: E G D H F I J.

Preorder after A: B C D E G F H I J.

Left subtree preorder: B C (since two nodes). Right subtree preorder: D E G F H I J.

Recursively build.

Postorder? After construction:

Left: B is root of left? Preorder B C → B root, C right child? Inorder B C → B left, C right? Actually inorder: B C → B then C, so B is leftmost? For subtree with preorder B C and inorder B C: root B, right child C.

Right subtree: preorder D E G F H I J, inorder E G D H F I J. Root D. In inorder: left of D: E G, right: H F I J. Preorder after D: E G F H I J. Left preorder: E G, right: F H I J.

Left of D: preorder E G, inorder E G → root E, right child G.

Right of D: preorder F H I J, inorder H F I J → root F, left: H, right: I J.

Then I J: preorder I J, inorder I J → root I, right child J.

So tree:

A

/ \

B D

\ / \

C E F

\   \  

 G   H  

      \  

       I  

        \  

         J  

Postorder: C B G E H I J F D A? Actually traverse: left subtree: B→C? Postorder of left: C then B. Right subtree: E→G? Actually right subtree of D: left H, right I→J. So postorder: left of D: E, then G? Wait: D's left child E has right child G. So postorder for E subtree: G then E. Then H, then I, then J, then F, then D. Then A. So: C, B, G, E, H, I, J, F, D, A. But given inorder and preorder, postorder should be: C B G E H I J F D A? Check: Inorder: B C A E G D H F I J. That seems not matching. Let's reconstruct carefully:

Inorder: B C A E G D H F I J

Preorder: A B C D E G F H I J

Root A.

In inorder, left of A: B C (indices 1-2), right: E G D H F I J (indices 4-10).

Left subtree: inorder B C, preorder B C → root B, right child C (since inorder B then C).

Right subtree: inorder E G D H F I J, preorder D E G F H I J → root D.

In inorder, left of D: E G (indices 4-5), right: H F I J (indices 7-10).

Left of D: inorder E G, preorder E G → root E, right child G.

Right of D: inorder H F I J, preorder F H I J → root F.

In inorder, left of F: H (index7), right: I J (indices9-10).

Left of F: H → single node.

Right of F: inorder I J, preorder H I J? Wait preorder after F: H I J. But preorder for right subtree of D is F H I J. So after F, we have H I J. But inorder for right of F is I J? Actually inorder: H F I J. So left of F is H, right is I J. Preorder: F then H then I J? But preorder is F H I J. So root F, left child H, right subtree I J.

Right subtree of F: inorder I J, preorder I J → root I, right child J.

So final tree:

    A  

   / \  

  B   D  

   \ / \  

    C E F  

     \   \  

      G   H  

           \  

            I  

             \  

              J  

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

But given inorder: B C A E G D H F I J. That matches: left: B C, root A, right: E G D H F I J. In right: E G left of D, H left of F? Actually inorder: E G D H F I J → E G (left of D), D, H (left of F), F, I J (right of F). Yes.

So postorder: C B G E H I J F D A.

AVL Trees

Balancing Condition: Height difference (balance factor) of left and right subtrees ≤ 1 for every node. Rotations:

• LL (Left-Left): Right rotate.

• RR (Right-Right): Left rotate.

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

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

Example (Jun 2022): Insert/delete with rebalancing (not provided here).

B-Trees

Properties (order m):

• Each node has at most m children, at least ⌈m/2⌉ children (except root).

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

• Keys in node sorted.

• All leaves at same level.

Insertion:

1. Search leaf where key should go.

2. Insert key in sorted order.

3. If overflow (m keys), split: median moves to parent, left/right become children.

Deletion Cases:

1. Key in leaf: Remove directly. If underflow (less than ⌈m/2⌉-1 keys), redistribute or merge.

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

3. Underflow after deletion:

   • Redistribution: Borrow from sibling.

   • Merge: Combine with sibling and pull down parent key.

Example (Jun 2023, Jun 2024): B-Tree deletion with cases.

2-3 Trees

Properties:

• 2-node: 1 key, 2 children.

• 3-node: 2 keys, 3 children.

• All leaves at same level.

• Insertion: Search leaf, add key (may cause split).

• Deletion: Replace with predecessor/successor, may cause merge.

Example (Jun 2023): Insertion/deletion.

Binomial Heaps

Properties:

• Collection of binomial trees (order k tree has $$\displaystyle 2^k $$ nodes).

• Root list: trees in increasing order of degree.

• No two trees have same degree.

• Linking: Make larger root child of smaller.

Union Operation:

1. Merge root lists by degree (like merging sorted lists).

2. Scan merged list: if two trees same degree, link (make one child of other).

3. Continue until no two same degree.

Find-Minimum:

• Scan root list (since all keys in roots, min among roots).

Example (Jun 2025): Asked to explain properties and write union algorithm.

VIII. Graph Algorithms

Traversals

BFS vs DFS:

Example (Jun 2023): Differentiate.

Topological Sorting

Using DFS:

1. Perform DFS, record finish times.

2. Order vertices by decreasing finish times.

Example (Jun 2022): Apply on given DAG.

Hamiltonian Cycle

Graph-specific approach: Use backtracking/branch and bound (refer to V/VI).

IX. NP-Completeness and Advanced Topics

Complexity Classes

• P: Problems solvable in polynomial time.

• NP: Problems verifiable in polynomial time (solutions checkable quickly).

• NP-complete: Problems in NP such that all NP problems reduce to them (hardest in NP). If any NPC solved in P, then P=NP.

• NP-hard: At least as hard as NPC, but not necessarily in NP (e.g., optimization versions).

Relationships:

P ⊆ NP, NPC ⊆ NP-hard, NPC = NP-hard ∩ NP.
Example Reduction (Jun 2024): Reduce SAT to Clique, etc.

Approximation Algorithms

• Performance Ratio: $$\displaystyle \rho = \frac{\text{approx cost}}{\text{optimal cost}} $$ (≥1 for minimization).

• Approximation Scheme: For any ε>0, algorithm with ratio (1+ε) in poly time (PTAS). Examples:

• TSP with Triangle Inequality: Nearest neighbor ratio ≤ log n? Actually 2-approx using MST doubling.

• Knapsack: Greedy by density gives 2-approx for 0/1? Actually PTAS exists.

Specialized Topics (Nov 2023, Dec 2024):

• Data Stream Algorithms: Handle high-velocity data using summaries (e.g., Bloom filters, count-min sketch).

• Data Transfer Optimization: Minimize cost/time in networks (e.g., max flow, multicommodity flow).

• Logic Optimization: Minimize Boolean functions (K-maps, Quine-McCluskey).

Parallel Algorithms

Purpose: Speedup, efficiency. Complexity Measures:

• Work (W): Total operations across all processors.

• Span (T∞): Longest path in dependency graph (critical path).

• Parallel Time (T_P): Time on P processors, $$\displaystyle T_P \geq T_\infty $$, $$\displaystyle T_P \geq W/P $$. Design Considerations: Decomposition (task/data), synchronization, load balancing.

X. Sorting and Order Statistics

Stable vs Unstable Sorting

Example (Jun 2025): Asked which are stable/unstable.

Heap Sort

Algorithm:

1. Build max-heap from array.

2. Repeat:

   • Swap root (max) with last element.

   • Reduce heap size by 1.

   • Heapify root. Complexity: $O(n \log n)$ (build heap $O(n)$, n extractions $O(n \log n)$).

Example (Nov 2023): Step-by-step on given data.

Optimal Merge Patterns

Reference to III.F: Same as Huffman but for file merging.

XI. Lower Bounds and Decision Trees

Lower Bound Theory

• Sorting: Any comparison-based sort requires $\Omega(n \log n)$ comparisons in worst case.

• Selection (min/max): $\Omega(n)$ comparisons.

• Matrix Multiplication: $$\displaystyle \Omega(n^2) $$ (trivial), but Strassen shows $$\displaystyle O(n^{2.81}) $$, best known $$\displaystyle O(n^{2.37}) $$.

Decision Trees

Model: Binary tree where each internal node is a comparison, leaves are permutations. Height: Minimum height ≥ $$\displaystyle \log_2(n!) $$ → $\Omega(n \log n)$ for sorting. Example (Jun 2022): Decision tree for 3-element selection sort. Selection sort for 3 elements: first find min among 3 (2 comparisons), then find min of remaining 2 (1 comparison). Total 3 comparisons. Decision tree has at least 6 leaves (3! permutations), height ≥ $$\displaystyle \log_2 6 \approx 2.58 $$, so at least 3 comparisons.