BSc CSIT (TU) Science Design and Analysis of Algorithms (BSc CSIT, CSC314) Question Paper 2074 Nepal

Divide and Conquer Strategy

Divide and conquer solves a problem in three steps:

1. Divide the problem into smaller subproblems of the same type.
2. Conquer each subproblem by solving it recursively (base case is solved directly).
3. Combine the solutions of the subproblems into a solution for the original problem.

Classic examples: merge sort, quicksort, binary search, Strassen's matrix multiplication.

Merge Sort Algorithm

MERGE-SORT(A, l, r):
    if l < r:
        m = (l + r) / 2          # divide
        MERGE-SORT(A, l, m)      # conquer left
        MERGE-SORT(A, m+1, r)    # conquer right
        MERGE(A, l, m, r)        # combine

MERGE(A, l, m, r):
    L = A[l..m]; R = A[m+1..r]   (append +inf sentinels)
    i = j = 0; k = l
    while elements remain in L and R:
        if L[i] <= R[j]: A[k++] = L[i++]
        else:            A[k++] = R[j++]
    copy remaining elements of L (or R) into A

Trace on [38, 27, 43, 3, 9, 82, 10]

Divide phase (split until single elements):

[38,27,43,3,9,82,10]
 -> [38,27,43,3] | [9,82,10]
 -> [38,27]|[43,3]   [9,82]|[10]
 -> [38][27] [43][3]  [9][82] [10]

Merge phase (combine in sorted order):

[38][27]      -> [27,38]
[43][3]       -> [3,43]
[27,38][3,43] -> [3,27,38,43]
[9][82]       -> [9,82]
[9,82][10]    -> [9,10,82]
[3,27,38,43] + [9,10,82] -> [3,9,10,27,38,43,82]

Sorted result: [3, 9, 10, 27, 38, 43, 82]

Time Complexity (Recurrence)

Let $T(n)$ be the running time. Dividing takes $O(1)$, two recursive calls on size $n/2$, and merging takes $\Theta(n)$:

By the Master Theorem with $a = 2,\ b = 2,\ f(n) = n$: since $n^{\log_b a} = n^{\log_2 2} = n = f(n)$, this is Case 2, giving

Merge sort runs in $\Theta(n \log n)$ in best, average and worst cases, using $O(n)$ extra space.

Dynamic Programming

Dynamic programming (DP) is a technique for solving problems that exhibit two properties:

• Optimal substructure — an optimal solution is built from optimal solutions of subproblems.
• Overlapping subproblems — the same subproblems recur many times.

DP solves each distinct subproblem once and stores its result in a table (memoization / bottom-up tabulation), avoiding recomputation.

Floyd-Warshall Algorithm (All-Pairs Shortest Paths)

Floyd-Warshall finds the shortest distance between every pair of vertices in a weighted graph (may have negative edges, but no negative cycles). It considers, for each intermediate vertex $k$, whether routing $i \to k \to j$ improves the current distance.

Recurrence. Let $d_{ij}^{(k)}$ be the shortest path from $i$ to $j$ using only intermediate vertices in $\{1,\dots,k\}$:

FLOYD-WARSHALL(W):           # W = weight matrix, n vertices
    D = W                    # D[i][j] = w(i,j), 0 on diagonal, inf if no edge
    for k = 1 to n:
        for i = 1 to n:
            for j = 1 to n:
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    return D

Example

Graph with vertices {1,2,3}, edges: 1→2 (8), 1→3 (5), 3→2 (2), 2→3 (1). Initial matrix ($\infty$ where no edge):

Using $k=3$ as intermediate: $d_{12} = \min(8,\ d_{13}+d_{32}) = \min(8, 5+2) = 7$. Final distance matrix:

Time Complexity

Three nested loops over $n$ vertices give

with $\Theta(n^2)$ space for the distance matrix.

Greedy Method

The greedy method builds a solution piece by piece, always choosing the option that looks best (locally optimal) at the current step, without reconsidering earlier choices. It yields a globally optimal solution when the problem has the greedy-choice property and optimal substructure (e.g., Huffman coding, fractional knapsack, MST, Dijkstra).

Huffman Coding for "CYBER CRIME"

Step 1 — Frequencies (the string is CYBER CRIME, including the space):

Total characters = 11.

Step 2 — Build the Huffman tree by repeatedly merging the two lowest-frequency nodes:

Merge Y(1)+B(1)            -> 2
Merge space(1)+I(1)        -> 2
Merge M(1)+C(2)            -> 3   (M is a leftover single, paired with C)
Merge (YB=2)+(space,I=2)   -> 4
Merge E(2)+R(2)            -> 4
Merge (MC=3)+(YB,space,I=4)-> 7
Merge (ER=4)+(...=7)       -> 11 (root)

Step 3 — Assign prefix codes (left = 0, right = 1). One valid optimal code:

Step 4 — Total bits to encode the string:

A fixed-length code for 8 symbols would need $\lceil\log_2 8\rceil = 3$ bits each $= 33$ bits here too; Huffman is optimal and never worse. (Exact codes may differ depending on tie-breaking, but the optimal total length is 33 bits.)

Binary Search (Divide and Conquer)

Binary search finds a key in a sorted array by repeatedly halving the search interval.

BINARY-SEARCH(A, l, r, key):     # A sorted ascending
    if l > r: return -1          # not found
    m = (l + r) / 2
    if A[m] == key: return m
    else if key < A[m]:
        return BINARY-SEARCH(A, l, m-1, key)   # search left half
    else:
        return BINARY-SEARCH(A, m+1, r, key)   # search right half

Complexity Analysis

Each step discards half the elements, giving the recurrence

So binary search runs in $O(\log n)$ in the worst and average cases and $O(1)$ in the best case, using $O(1)$ extra space (iterative) or $O(\log n)$ stack space (recursive).

Randomized Quicksort

Randomized quicksort is quicksort that selects the pivot uniformly at random from the current subarray instead of always taking a fixed position. This makes the running time independent of the input order, so no specific input can force worst-case behaviour.

RANDOMIZED-PARTITION(A, p, r):
    i = RANDOM(p, r)        # random index
    swap A[i] with A[r]
    return PARTITION(A, p, r)   # standard Lomuto/Hoare partition

RANDOMIZED-QUICKSORT(A, p, r):
    if p < r:
        q = RANDOMIZED-PARTITION(A, p, r)
        RANDOMIZED-QUICKSORT(A, p, q-1)
        RANDOMIZED-QUICKSORT(A, q+1, r)

Expected Time Complexity

The total work is dominated by element comparisons. Let $X_{ij}$ indicate that elements of ranks $i$ and $j$ are compared. Two elements are compared iff one of them is the first among ranks $i..j$ to be chosen as a pivot, so

The expected number of comparisons is

Hence the expected running time is $O(n\log n)$. The worst case is still $\Theta(n^2)$ (extremely unlikely), and space is $O(\log n)$ expected stack depth.

Fractional Knapsack — Greedy Algorithm

In the fractional knapsack problem, items may be taken in fractions. The greedy strategy picks items in decreasing order of value-to-weight ratio $v_i / w_i$, taking as much of each as fits.

FRACTIONAL-KNAPSACK(v[], w[], n, W):
    for each item i: ratio[i] = v[i] / w[i]
    sort items by ratio in decreasing order
    totalValue = 0; cap = W
    for each item i in sorted order:
        if w[i] <= cap:
            take whole item: cap -= w[i]; totalValue += v[i]
        else:
            take fraction: totalValue += v[i] * (cap / w[i]); cap = 0
            break
    return totalValue

This greedy choice is optimal because swapping any quantity from a lower-ratio item to a higher-ratio one never decreases total value (greedy-choice property).

Time Complexity

• Computing ratios: $O(n)$.
• Sorting by ratio: $O(n \log n)$ — the dominant cost.
• Single pass to fill the knapsack: $O(n)$.

Edit Distance: "ARTIFICIAL" → "NATURAL"

The edit (Levenshtein) distance is the minimum number of insertions, deletions and substitutions to convert one string into another. DP recurrence with $d[i][j]$ = distance between first $i$ chars of $X$ and first $j$ chars of $Y$:

with $d[i][0]=i$ and $d[0][j]=j$.

Here $X =$ ARTIFICIAL (m = 10), $Y =$ NATURAL (n = 7). Filling the $11 \times 8$ table (rows = ARTIFICIAL, cols = NATURAL):

Result

It takes a minimum of 7 operations to transform ARTIFICIAL into NATURAL. The DP runs in $O(mn)$ time and space.

Dijkstra's Algorithm (Single-Source Shortest Paths)

Dijkstra finds shortest paths from a source $s$ to all vertices in a graph with non-negative edge weights. It greedily extracts the closest unfinalized vertex and relaxes its outgoing edges.

DIJKSTRA(G, w, s):
    for each vertex v: dist[v] = inf; prev[v] = nil
    dist[s] = 0
    Q = all vertices (min-priority queue keyed by dist)
    while Q not empty:
        u = EXTRACT-MIN(Q)        # closest unprocessed vertex
        for each edge (u, v):
            if dist[u] + w(u,v) < dist[v]:   # relax
                dist[v] = dist[u] + w(u,v)
                prev[v] = u
    return dist, prev

Example

Graph: edges A→B(4), A→C(1), C→B(2), C→D(5), B→D(1). Source = A.

Shortest distances from A: A=0, C=1, B=3 (via A→C→B), D=4 (via A→C→B→D).

Complexity

With a binary-heap priority queue: $O((V+E)\log V)$; with an array: $O(V^2)$.

Matrix Chain Multiplication Problem

Given a chain of matrices $A_1, A_2, \dots, A_n$ where $A_i$ has dimension $p_{i-1} \times p_i$, matrix multiplication is associative, so the product can be parenthesized in many ways. Each way yields the same result but a different number of scalar multiplications. The goal is to find the parenthesization that minimizes the total scalar multiplications (multiplying a $p \times q$ by $q \times r$ matrix costs $p\,q\,r$).

Dynamic Programming Formulation

Let $m[i][j]$ = minimum cost to multiply $A_i \cdots A_j$. The optimal split places the last multiplication at some $k$ ($i \le k < j$):

MATRIX-CHAIN-ORDER(p[0..n]):
    for i = 1 to n: m[i][i] = 0
    for len = 2 to n:                 # chain length
        for i = 1 to n-len+1:
            j = i + len - 1
            m[i][j] = inf
            for k = i to j-1:
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]
                if q < m[i][j]:
                    m[i][j] = q; s[i][j] = k   # store split for parenthesization
    return m, s

The table $s[i][j]$ records the optimal split point so the parenthesization can be reconstructed.

Complexity

Three nested loops give $O(n^3)$ time and $O(n^2)$ space — far better than the exponential number of possible parenthesizations.

Heap Sort

Heap sort uses a binary max-heap (a complete binary tree where each parent ≥ its children, stored in an array). It (1) builds a max-heap, then (2) repeatedly swaps the root (max) to the end and re-heapifies the reduced heap.

HEAPIFY(A, n, i):           # sift down node i in a heap of size n
    largest = i; l = 2i+1; r = 2i+2
    if l < n and A[l] > A[largest]: largest = l
    if r < n and A[r] > A[largest]: largest = r
    if largest != i:
        swap A[i], A[largest]; HEAPIFY(A, n, largest)

HEAP-SORT(A, n):
    for i = n/2 - 1 downto 0: HEAPIFY(A, n, i)   # build max-heap
    for i = n-1 downto 1:
        swap A[0], A[i]          # move max to the end
        HEAPIFY(A, i, 0)         # restore heap on A[0..i-1]

Example: sort [4, 10, 3, 5, 1]

Build max-heap: → [10, 5, 3, 4, 1]

Extract maxima:

swap 10,1 -> [1,5,3,4 | 10], heapify -> [5,4,3,1 | 10]
swap 5,1  -> [1,4,3 | 5,10], heapify -> [4,1,3 | 5,10]
swap 4,3  -> [3,1 | 4,5,10], heapify -> [3,1 | ...]
swap 3,1  -> [1 | 3,4,5,10]

Sorted: [1, 3, 4, 5, 10].

Time Complexity

• BUILD-HEAP: $O(n)$.
• $n-1$ extractions, each with a $O(\log n)$ heapify: $O(n \log n)$.

with $O(1)$ extra space (in-place).

Subset-Sum via Backtracking

Problem. Given a set of positive integers and a target sum $S$, find a subset whose elements add up to $S$.

Backtracking idea. Build the subset incrementally. At each element decide to include or exclude it, extending the partial sum. Prune a branch when:

• the running sum exceeds $S$ (overshoot), or
• the running sum plus all remaining elements is still $< S$ (cannot reach target).

SUBSET-SUM(w[], i, currSum, target, remaining):
    if currSum == target: report solution; return
    if i == n or currSum > target: return
    if currSum + remaining < target: return   # bound
    # include w[i]
    SUBSET-SUM(w, i+1, currSum + w[i], target, remaining - w[i])
    # exclude w[i]
    SUBSET-SUM(w, i+1, currSum, target, remaining - w[i])

Example

Set = {3, 4, 5, 6}, target $S = 9$.

{} (0)
 |-- +3 (3)
 |     |-- +4 (7) -> +5=12 (prune>9), -5 then +6=13 (prune)
 |     |-- skip4 -> +5=8 -> +6=14(prune); skip5 -> +6=9  SOLUTION {3,6}
 |-- skip3
        |-- +4 (4) -> +5=9  SOLUTION {4,5}

Solutions found: {3, 6} and {4, 5}, each summing to 9.

The state-space tree has $2^n$ nodes in the worst case, so worst-case time is $O(2^n)$, but pruning prunes large portions in practice.

Approximation Algorithms

Many optimization problems are NP-hard, so no known polynomial-time algorithm finds the exact optimum. An approximation algorithm runs in polynomial time and returns a solution provably close to optimal. For a minimization problem, an algorithm has approximation ratio $\rho$ if for every input

Vertex Cover Approximation (2-approximation)

A vertex cover is a set of vertices that touches every edge. Finding the minimum vertex cover is NP-hard. The classic 2-approximation repeatedly picks an uncovered edge and adds both its endpoints:

APPROX-VERTEX-COVER(G):
    C = {}
    E' = edges of G
    while E' != empty:
        pick any edge (u, v) from E'
        C = C union {u, v}
        remove from E' every edge incident to u or v
    return C

Why ratio 2

The edges $(u,v)$ picked in the loop form a matching (no two share a vertex). Any vertex cover must include at least one endpoint of every matched edge, so $|\text{OPT}| \ge$ (number of matched edges) $= |C|/2$. Therefore

so this is a 2-approximation, running in $O(V + E)$ time.