Design & Analysis of Algorithms 2023

Answer: (ii) O(n²)

Solution: The dominant term in 5n² + 3n is 5n², so f(n) = O(n²).

Answer: (ii) O(log n)

Solution: By Master theorem: a=1, b=2, f(n)=1. n^(log_b(a)) = n⁰ = 1. Since f(n) = Θ(1), Case 2 gives T(n) = Θ(log n).

Answer: (ii) Directed Acyclic Graphs (DAG)

Solution: Topological sort requires a linear ordering of vertices such that for every directed edge (u,v), u comes before v. This is only possible if the graph has no cycles.

Answer: (iii) Merge Sort

Solution: Merge Sort preserves the relative order of equal elements, making it a stable sorting algorithm.

Answer: (ii) Negative edge weights

Solution: Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative edge weights and can detect negative weight cycles.

Answer: (iii) O(n)

Solution: Merge sort requires O(n) extra space for the temporary arrays used during the merge operation.

Answer: (ii) Optimal substructure

Solution: Dynamic programming requires optimal substructure (optimal solution contains optimal solutions to subproblems) and overlapping subproblems.

Answer: (i) O(n + k)

Solution: Counting sort runs in O(n + k) time where n is the number of elements and k is the range of input values. It's a non-comparison based sort.

Answer: (ii) Find the average time per operation over a sequence of operations

Solution: Amortized analysis determines the average cost of operations in a sequence, even though some individual operations may be expensive.

Answer: (ii) NP-Complete

Solution: The Hamiltonian path problem (determining if a path visiting each vertex exactly once exists) is a classic NP-Complete problem.

Answer:

Master Theorem: For recurrence T(n) = aT(n/b) + f(n), where a ≥ 1, b > 1:

Let c = log_b(a)

Case 1: If f(n) = O(n^(c-ε)) for some ε > 0, then T(n) = Θ(n^c)

Case 2: If f(n) = Θ(n^c · log^k(n)) for k ≥ 0, then T(n) = Θ(n^c · log^(k+1)(n))

Case 3: If f(n) = Ω(n^(c+ε)) for some ε > 0, and af(n/b) ≤ cf(n) for c < 1, then T(n) = Θ(f(n))

Solving T(n) = 4T(n/2) + n²:

Here a = 4, b = 2, f(n) = n² c = log₂(4) = 2

Compare f(n) = n² with n^c = n²: f(n) = Θ(n² · log⁰(n)) → Case 2 with k = 0

T(n) = Θ(n² log n)

Answer:

Algorithm:

MAX-MIN(A, low, high)
    if low = high          // one element
        return (A[low], A[low])
    if high = low + 1      // two elements
        if A[low] < A[high]
            return (A[high], A[low])
        else
            return (A[low], A[high])
    mid = ⌊(low + high) / 2⌋
    (max1, min1) = MAX-MIN(A, low, mid)
    (max2, min2) = MAX-MIN(A, mid+1, high)
    return (max(max1, max2), min(min1, min2))

Recurrence: T(n) = 2T(n/2) + 2

Number of comparisons:

• T(n) = 2T(n/2) + 2
• T(2) = 1, T(1) = 0
• Solution: T(n) = 3n/2 - 2

Comparison with naive approach:

• Naive: 2(n-1) = 2n - 2 comparisons
• Divide & Conquer: 3n/2 - 2 comparisons
• Savings: n/2 comparisons

Answer:

LCS Problem: Find the longest subsequence that is common to two sequences.

DP Recurrence:

c[i,j] = 0                          if i=0 or j=0
c[i,j] = c[i-1,j-1] + 1            if X[i] = Y[j]
c[i,j] = max(c[i-1,j], c[i,j-1])   if X[i] ≠ Y[j]

DP Table for X = "ABCBDAB", Y = "BDCAB":

LCS Length = 4 LCS = "BCAB"

Time Complexity: O(m × n), Space: O(m × n)

Answer:

Problem: Given n keys with known search probabilities, construct a BST that minimizes the expected search cost.

DP Formulation:

• e[i,j] = expected cost of searching an optimal BST containing keys kᵢ ... kⱼ
• w[i,j] = sum of probabilities p[i] to p[j]
• e[i,j] = min_{i≤r≤j} {e[i,r-1] + e[r+1,j] + w[i,j]}

Example: Keys k₁=10, k₂=20, k₃=30 with probabilities p₁=0.3, p₂=0.2, p₃=0.5

Base cases: e[i,i-1] = 0 for all i

Length 1:

• e[1,1] = p₁ = 0.3
• e[2,2] = p₂ = 0.2
• e[3,3] = p₃ = 0.5

Length 2:

• e[1,2] = min{e[1,0]+e[2,2]+0.5, e[1,1]+e[3,2]+0.5} = min{0.7, 0.8} = 0.7
• e[2,3] = min{e[2,1]+e[3,3]+0.7, e[2,2]+e[4,3]+0.7} = min{1.2, 0.9} = 0.9

Length 3:

• e[1,3] = min over r=1,2,3
  • r=1: 0 + 0.9 + 1.0 = 1.9
  • r=2: 0.3 + 0.5 + 1.0 = 1.8
  • r=3: 0.7 + 0 + 1.0 = 1.7 ✓

Minimum expected cost = 1.7 with k₃ as root

Answer:

Fractional Knapsack: Unlike 0/1 knapsack, items can be broken into fractions. Greedy approach works optimally.

Greedy Strategy: Sort items by value-to-weight ratio (value/weight) in decreasing order, then select items greedily.

Given:

Sorted by ratio: Item 1 (6.0), Item 2 (5.0), Item 3 (4.0)

Selection:

1. Take Item 1 completely: Weight = 10, Value = 60, Remaining = 40
2. Take Item 2 completely: Weight = 20, Value = 100, Remaining = 20
3. Take Item 3 partially: 20/30 = 2/3 fraction, Value = 120 × 2/3 = 80

Total Value = 60 + 100 + 80 = 240 Total Weight = 10 + 20 + 20 = 50 ✓

Answer:

Huffman Coding: A greedy algorithm for data compression that assigns variable-length prefix-free codes to characters based on frequencies.

Construction for a:5, b:9, c:12, d:13, e:16, f:45:

Step 1: Combine a(5) and b(9) → node(14) Step 2: Combine c(12) and d(13) → node(25) Step 3: Combine node(14) and e(16) → node(30) Step 4: Combine node(25) and node(30) → node(55) Step 5: Combine f(45) and node(55) → root(100)

Huffman Codes:

Weighted path length = 45×1 + 12×3 + 13×3 + 5×4 + 9×4 + 16×3 = 45+36+39+20+36+48 = 224 bits

Answer:

Bellman-Ford Algorithm:

BELLMAN-FORD(G, w, s)
    // Initialize
    for each vertex v ∈ V
        d[v] = ∞
        π[v] = NIL
    d[s] = 0
    
    // Relax all edges V-1 times
    for i = 1 to |V| - 1
        for each edge (u,v) ∈ E
            if d[v] > d[u] + w(u,v)
                d[v] = d[u] + w(u,v)
                π[v] = u
    
    // Check for negative weight cycles
    for each edge (u,v) ∈ E
        if d[v] > d[u] + w(u,v)
            return FALSE  // Negative cycle detected
    return TRUE

Negative Cycle Detection: After V-1 iterations, if any edge can still be relaxed, it means a negative weight cycle exists. This is because in a graph without negative cycles, V-1 iterations are sufficient to find shortest paths (longest simple path has at most V-1 edges).

Time Complexity: O(V × E) Space Complexity: O(V)

Answer:

DFS Algorithm:

DFS(G)
    for each vertex u ∈ V
        color[u] = WHITE
        π[u] = NIL
    time = 0
    for each vertex u ∈ V
        if color[u] = WHITE
            DFS-VISIT(u)

DFS-VISIT(u)
    time = time + 1
    d[u] = time      // discovery time
    color[u] = GRAY
    for each v adjacent to u
        if color[v] = WHITE
            π[v] = u
            DFS-VISIT(v)
    color[u] = BLACK
    time = time + 1
    f[u] = time       // finish time

Example: Graph with vertices {A,B,C,D,E} and edges {A→B, A→C, B→D, C→D, D→E}

DFS from A:

1. Visit A (d=1), explore B
2. Visit B (d=2), explore D
3. Visit D (d=3), explore E
4. Visit E (d=4), finish E (f=5)
5. Finish D (f=6), finish B (f=7)
6. Explore C from A
7. Visit C (d=8), D already visited
8. Finish C (f=9), finish A (f=10)

DFS Order: A → B → D → E → C

Applications:

1. Topological sorting
2. Cycle detection
3. Strongly connected components
4. Path finding
5. Solving puzzles (mazes)

Answer:

KMP Algorithm: Efficient string matching that avoids redundant comparisons by using a prefix function (failure function).

Failure Function (π): π[i] = length of longest proper prefix of P[1..i] that is also a suffix.

Computing π for P = "ABABACA":

π = [0, 0, 1, 2, 3, 0, 1]

KMP Matching:

KMP-MATCHER(T, P)
    n = |T|, m = |P|
    Compute prefix function π
    q = 0
    for i = 1 to n
        while q > 0 and P[q+1] ≠ T[i]
            q = π[q]
        if P[q+1] = T[i]
            q = q + 1
        if q = m
            print "Match at" i-m
            q = π[q]

Time Complexity: O(n + m) — linear time

Answer:

When KMP is significantly better:

1. Repetitive patterns: When pattern has repeated substrings (e.g., "AAAA"), naive algorithm backtracks many times while KMP uses the prefix function.

2. Repetitive text: Text like "AAAAAAAAB" with pattern "AAAB" — naive does many unnecessary comparisons.

3. DNA/Protein sequences: Biological sequences with limited alphabet (4 or 20 characters) have many partial matches.

4. Large-scale text search: Searching in large documents, log files, or databases where O(nm) is prohibitive.

Example: Text = "AAAAAAAAB", Pattern = "AAAB"

• Naive: Compares AAAB at each position, O(nm) = O(36)
• KMP: Uses prefix function, O(n+m) = O(13)

Answer:

Problem: Find all subsets of S whose elements sum to d = 9.

State-space tree exploration with pruning:

Sort S = {1, 2, 5, 6, 8}

Backtracking with bounding:

• Include/exclude each element
• Prune if: current sum > d (exceeded) or current sum + remaining < d (can't reach)

Solutions found:

1. {1, 2, 6}: 1 + 2 + 6 = 9 ✓
2. {1, 8}: 1 + 8 = 9 ✓
3. {3, 6}: Not possible (3 ∉ S)

Wait, let's redo:

• {1, 2, 6}: 1+2+6 = 9 ✓
• {1, 8}: 1+8 = 9 ✓

State-space tree (partial):

Level 0: sum=0
├── Include 1 (sum=1)
│   ├── Include 2 (sum=3)
│   │   ├── Include 5 (sum=8)
│   │   │   ├── Include 6 (sum=14 > 9, PRUNE)
│   │   ├── Exclude 5 (sum=3)
│   │   │   ├── Include 6 (sum=9 ✓ SOLUTION {1,2,6})
│   ├── Exclude 2 (sum=1)
│   │   ├── Include 5 (sum=6)
│   │   │   ├── Include 6 (sum=12 > 9, PRUNE)
│   │   ├── Exclude 5 (sum=1)
│   │   │   ├── Include 6 (sum=7)
│   │   │   │   ├── Include 8 (sum=15 > 9, PRUNE)
│   │   │   ├── Exclude 6 (sum=1)
│   │   │   │   ├── Include 8 (sum=9 ✓ SOLUTION {1,8})

Solutions: {1,2,6} and {1,8}

Answer:

Graph Coloring Problem: Assign m colors to vertices of a graph such that no two adjacent vertices have the same color.

Backtracking Algorithm:

GRAPH-COLOR(k)
    // Try to color vertex k
    repeat
        NextColor(k)    // Find next valid color
        if color[k] = 0
            return      // No valid color, backtrack
        if k = n
            print solution
        else
            GRAPH-COLOR(k+1)

NextColor(k)
    repeat
        color[k] = (color[k] + 1) mod (m+1)
        if color[k] = 0
            return  // All colors exhausted
        // Check if color is valid
        valid = true
        for each vertex j adjacent to k
            if color[j] = color[k]
                valid = false
                break
    until valid

Example: Graph with 4 vertices, edges: (1,2), (1,3), (2,3), (2,4), (3,4), 3 colors: R, G, B

Solution:

• Vertex 1: R
• Vertex 2: G (adjacent to 1/R, so not R)
• Vertex 3: B (adjacent to 1/R and 2/G, so not R or G)
• Vertex 4: R (adjacent to 2/G and 3/B, so not G or B)

Coloring: {1:R, 2:G, 3:B, 4:R} ✓

Answer:

Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices using dynamic programming.

Algorithm:

FLOYD-WARSHALL(W)
    n = |V|
    D⁰ = W    // Initialize with edge weights
    for k = 1 to n
        for i = 1 to n
            for j = 1 to n
                D^k[i,j] = min(D^(k-1)[i,j], D^(k-1)[i,k] + D^(k-1)[k,j])
    return D^n

Key Idea: In iteration k, consider whether using vertex k as an intermediate vertex improves the shortest path from i to j.

Example: 3 vertices, edges: 1→2(3), 1→3(8), 2→3(2), 3→1(5)

D⁰ (initial):

     1    2    3
1  [ 0    3    8  ]
2  [ ∞    0    2  ]
3  [ 5    ∞    0  ]

D¹ (through vertex 1):

     1    2    3
1  [ 0    3    8  ]
2  [ ∞    0    2  ]
3  [ 5    8    0  ]  // 3→2 via 1: 5+3=8

D² (through vertices 1,2):

     1    2    3
1  [ 0    3    5  ]  // 1→3 via 2: 3+2=5
2  [ ∞    0    2  ]
3  [ 5    8    0  ]

D³ (through vertices 1,2,3):

     1    2    3
1  [ 0    3    5  ]
2  [ 7    0    2  ]  // 2→1 via 3: 2+5=7
3  [ 5    8    0  ]

Time Complexity: O(V³), Space: O(V²)

Answer:

Travelling Salesman Problem (TSP): Given n cities and distances between each pair, find the shortest tour that visits every city exactly once and returns to the starting city.

DP Solution (Held-Karp):

• State: (S, i) = minimum cost to visit all cities in set S ending at city i
• C(S, i) = min_{j∈S, j≠i} {C(S-{i}, j) + d(j, i)}
• Time: O(2ⁿ × n²), Space: O(2ⁿ × n)

Why TSP is NP-Hard:

1. Decision version is NP-Complete: Given a distance matrix and a bound B, is there a tour of total length ≤ B? This decision problem is NP-Complete.

2. Reduction from Hamiltonian Cycle: The Hamiltonian cycle problem (known NP-Complete) can be reduced to TSP in polynomial time. Given a graph G, create a distance matrix where d(i,j) = 1 if edge exists, 2 otherwise. A Hamiltonian cycle exists iff there's a tour of length n.

3. No known polynomial-time algorithm: Despite decades of research, no polynomial-time algorithm exists for TSP (unless P = NP).

4. Exponential number of tours: There are (n-1)!/2 possible tours for n cities, making brute force infeasible.

Approximation: For metric TSP (triangle inequality holds):

• Nearest neighbor heuristic: within factor 2 of optimal
• Christofides' algorithm: within factor 1.5 of optimal

Answer:

Red-Black trees are self-balancing BSTs with the following properties:

1. Every node is either Red or Black
2. Root is always Black
3. Every leaf (NIL) is Black
4. If a node is Red, both children are Black (no consecutive reds)
5. Every path from root to leaf has the same number of black nodes (black-height)

Operations: All in O(log n) time

• Search: Standard BST search
• Insert: Insert as red, fix violations with rotations and recoloring
• Delete: Complex, uses rotations and recoloring

Height bound: h ≤ 2 log₂(n+1)

Advantages:

• Guaranteed O(log n) worst-case operations
• Used in: Java TreeMap, C++ STL map, Linux kernel

Answer:

Approximation algorithms find near-optimal solutions to NP-Hard problems in polynomial time.

Approximation Ratio (ρ): For minimization: C/C* ≤ ρ(n) For maximization: C*/C ≤ ρ(n) Where C = algorithm's cost, C* = optimal cost

Examples:

1. Vertex Cover (2-approximation): Pick any edge, add both endpoints, remove covered edges. Gives solution ≤ 2 × optimal.

2. TSP (Christofides 1.5-approximation): MST + minimum weight perfect matching on odd-degree vertices. Cost ≤ 1.5 × optimal.

3. Set Cover (ln n approximation): Greedy selection of set covering most uncovered elements.

PTAS (Polynomial Time Approximation Scheme): For any ε > 0, provides (1+ε)-approximation in polynomial time.

Answer:

Amortized analysis finds the average cost per operation over a worst-case sequence of operations.

Methods:

1. Aggregate Method: Total cost of n operations / n
2. Accounting Method: Assign amortized costs; "save" extra cost for expensive operations
3. Potential Method: Define potential function Φ; amortized cost = actual cost + ΔΦ

Example (Dynamic Array Doubling):

• Most insertions: O(1)
• Occasional doubling: O(n) when array is full
• Amortized cost per insertion: O(1)

Proof using accounting: Charge 3 units per insertion. 1 for insertion, 2 saved for future copy when doubling. Total for n insertions = 3n = O(n), so amortized = O(1) per operation.

Answer:

Maximum Flow Problem: Find the maximum flow from source s to sink t in a flow network.

Ford-Fulkerson Method:

1. Start with zero flow
2. While there exists an augmenting path from s to t in residual graph:
   • Find bottleneck (minimum residual capacity) along the path
   • Augment flow along the path by bottleneck value
3. Return total flow

Key Concepts:

• Residual Graph: Shows remaining capacity on each edge
• Augmenting Path: Path from s to t with positive residual capacity
• Max-Flow Min-Cut Theorem: Maximum flow = Minimum cut capacity

Time Complexity: O(E × |f*|) where f* is max flow value Edmonds-Karp (BFS): O(V × E²)