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

Complexity Classes

Class P (Polynomial time)

The set of decision problems that can be solved by a deterministic algorithm in polynomial time $O(n^k)$. These are considered tractable.

Examples: sorting, searching, shortest path (Dijkstra), minimum spanning tree.

Class NP (Nondeterministic Polynomial time)

The set of decision problems for which a given certificate (proposed solution) can be verified in polynomial time by a deterministic algorithm. Equivalently, solvable in polynomial time on a nondeterministic machine.

Examples: SAT, Hamiltonian cycle, subset-sum, graph colouring. Note $P \subseteq NP$.

NP-Hard

A problem $H$ is NP-Hard if every problem in NP reduces to it in polynomial time. It is "at least as hard as the hardest problems in NP" but need not be in NP (need not even be a decision problem).

Examples: Halting problem, Travelling Salesman optimization problem.

NP-Complete

A problem is NP-Complete if it is (1) in NP and (2) NP-Hard. These are the hardest problems in NP; if any one is solved in polynomial time then $P = NP$.

Examples: SAT (Cook-Levin theorem), 3-SAT, Hamiltonian cycle, vertex cover, clique.

Proving a Problem is NP-Complete

To prove a problem $X$ is NP-Complete:

1. Show $X \in NP$: give a polynomial-time verifier — i.e., show that a candidate solution can be checked in polynomial time.
2. Show $X$ is NP-Hard: pick a known NP-Complete problem $Y$ and construct a polynomial-time reduction $Y \le_p X$:
   • Describe a polynomial-time transformation $f$ that maps any instance $y$ of $Y$ into an instance $f(y)$ of $X$.
   • Prove the equivalence: $y$ is a YES-instance of $Y$ iff $f(y)$ is a YES-instance of $X$.
3. Since $Y$ is NP-Complete and $Y \le_p X$, $X$ is NP-Hard. Combined with step 1, $X$ is NP-Complete.

Reduction works because polynomial-time reductions are transitive: every problem in NP reduces to $Y$, and $Y$ reduces to $X$, so every NP problem reduces to $X$.

Example: 3-SAT $\le_p$ Clique establishes that Clique is NP-Complete.

0/1 Knapsack — Dynamic Programming

Problem: Given $n$ items with weights $w_i$ and values $v_i$, and capacity $W$, select a subset (each item 0 or 1 time) maximizing total value subject to total weight $\le W$.

Recurrence

Let $K[i][j]$ = max value using the first $i$ items with capacity $j$.

Algorithm

Knapsack01(w[1..n], v[1..n], W):
  for j = 0 to W: K[0][j] = 0
  for i = 1 to n:
    for j = 0 to W:
      if w[i] > j: K[i][j] = K[i-1][j]
      else: K[i][j] = max(K[i-1][j], v[i] + K[i-1][j - w[i]])
  return K[n][W]

Time complexity: $O(nW)$ (pseudo-polynomial), space $O(nW)$.

Solving the instance

Items: weights $\{2,3,4,5\}$, values $\{3,4,5,6\}$, $W=5$.

Optimal value $= K[4][5] = 7$.

Backtracking the items

$K[4][5]=K[3][5]=K[2][5]=7$ (items 4 and 3 not used). $K[2][5]=7 \ne K[1][5]=3$, so item 2 (w=3, v=4) is taken; remaining capacity $5-3=2$. $K[1][2]=3 \ne K[0][2]=0$, so item 1 (w=2, v=3) is taken.

Selected items: {item 1 (w2,v3), item 2 (w3,v4)}, total weight = 5, total value = 7.

Divide and Conquer Strategy

A design paradigm with three steps:

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

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

Merge Sort Algorithm

MergeSort(A, l, r):
  if l < r:
    m = (l + r) / 2
    MergeSort(A, l, m)
    MergeSort(A, m+1, r)
    Merge(A, l, m, r)

Merge(A, l, m, r):       // merge two sorted halves
  copy A[l..m] -> L, A[m+1..r] -> R
  i = j = 0; k = l
  while i < |L| and j < |R|:
    if L[i] <= R[j]: A[k++] = L[i++]
    else:            A[k++] = R[j++]
  copy remaining L and R into A

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

Divide:

• [38,27,43,3] | [9,82,10]
• [38,27]|[43,3] and [9,82]|[10]
• [38]|[27], [43]|[3], [9]|[82], [10]

Conquer/Merge (bottom-up):

• [27,38], [3,43], [9,82], [10]
• [3,27,38,43], [9,10,82]
• Final: [3, 9, 10, 27, 38, 43, 82]

Time Complexity

The recurrence is:

where $\Theta(n)$ is the merge cost. By the Master Theorem with $a=2,\,b=2,\,f(n)=\Theta(n)$: $n^{\log_b a}=n^{1}=n$, so case 2 gives

This holds for best, average and worst cases. Space complexity is $O(n)$ (auxiliary), and merge sort is stable.

Job Sequencing with Deadlines

Problem: Given $n$ jobs, each with a deadline $d_i$ and profit $p_i$, where each job takes one unit of time and only one job runs at a time. Schedule a subset of jobs to maximize total profit, where a job earns its profit only if completed by its deadline.

Greedy Approach

1. Sort jobs in decreasing order of profit.
2. Find the maximum deadline $d_{max}$; create $d_{max}$ time slots, all free.
3. For each job (highest profit first): place it in the latest free slot $\le$ its deadline. If found, schedule the job; otherwise reject it.

JobSequencing(jobs):
  sort jobs by profit (desc)
  slot[1..dmax] = free
  for each job j:
    for t = min(dmax, j.deadline) down to 1:
      if slot[t] free: slot[t] = j; break

Example

Jobs: J1(d=2,p=100), J2(d=1,p=19), J3(d=2,p=27), J4(d=1,p=25), J5(d=3,p=15).

Sort by profit: J1(100), J3(27), J4(25), J2(19), J5(15). Max deadline = 3 → slots [1,2,3].

• J1 (d=2): slot 2 free → place at 2.
• J3 (d=2): slot 2 taken → slot 1 free → place at 1.
• J4 (d=1): slot 1 taken → reject.
• J2 (d=1): slot 1 taken → reject.
• J5 (d=3): slot 3 free → place at 3.

Schedule: slot1=J3, slot2=J1, slot3=J5. Sequence J3 → J1 → J5, total profit = 27 + 100 + 15 = 142.

Time complexity: $O(n^2)$ (or $O(n \log n)$ using a disjoint-set for slot allocation).

Naive String Matching

Slide the pattern $P$ (length $m$) over the text $T$ (length $n$) one position at a time and, at each shift, compare characters one by one.

NaiveMatch(T, P):
  for s = 0 to n - m:
    if P[1..m] == T[s+1 .. s+m]:
      report match at shift s

• Worst case: $O((n-m+1)\cdot m) = O(nm)$ (e.g. $T=aaaa\ldots a$, $P=aaab$).
• Best case: $O(n)$ when first character rarely matches.
• No preprocessing, $O(1)$ extra space.

Rabin-Karp Algorithm

Uses hashing to avoid full comparisons. Compute a hash of $P$ and of each length-$m$ window of $T$; only when hashes match do we verify character by character.

A rolling hash updates the window hash in $O(1)$:

where $d$ is the alphabet size and $q$ a prime.

RabinKarp(T, P, d, q):
  compute hp = hash(P), ht = hash(T[1..m])
  for s = 0 to n - m:
    if ht == hp and T[s+1..s+m] == P: report match
    update ht to next window (rolling hash)

Time complexity:

• Average / best case: $O(n + m)$ when there are few spurious hash collisions.
• Worst case: $O(nm)$ when many hash collisions force verification (e.g. all hashes equal).
• Preprocessing $O(m)$, extra space $O(1)$.

Binary Search (Divide and Conquer)

Works on a sorted array. Compare the target $x$ with the middle element; recurse into the left or right half, halving the search space each step.

BinarySearch(A, low, high, x):
  if low > high: return -1        // not found
  mid = (low + high) / 2
  if A[mid] == x: return mid
  else if x < A[mid]: return BinarySearch(A, low, mid-1, x)
  else:               return BinarySearch(A, mid+1, high, x)

Time Complexity Analysis

The recurrence (one half is discarded, comparison is $O(1)$):

By the Master Theorem ($a=1, b=2, f(n)=\Theta(1)$, $n^{\log_b a}=n^0=1$, case 2): $T(n)=\Theta(\log n)$.

• Best case: $O(1)$ — target is the middle element on the first comparison.
• Worst case: $O(\log n)$ — target absent or found only at the last level.
• Average case: $O(\log n)$ — expected number of comparisons is about $\log_2 n - 1$.

Space: $O(\log n)$ for recursion stack, or $O(1)$ iteratively.

Randomized Quicksort

Quicksort partitions an array around a pivot, recursively sorting the two parts. In randomized quicksort the pivot is chosen uniformly at random from the subarray, which makes the expected running time independent of input order and avoids the deterministic worst case on already-sorted data.

RandomizedQuicksort(A, p, r):
  if p < r:
    i = Random(p, r)         // random pivot index
    swap A[i], A[r]
    q = Partition(A, p, r)    // standard Lomuto/Hoare partition
    RandomizedQuicksort(A, p, q-1)
    RandomizedQuicksort(A, q+1, r)

Expected Time Complexity

Let $X$ be the total number of comparisons. Element ranks $z_i, z_j$ are compared at most once, with probability

Summing the expectations:

Using harmonic-number bounds, $E[X] \le 2n\,H_n = O(n\log n)$.

• Expected (average) time: $\Theta(n \log n)$.
• Worst case: $O(n^2)$ (extremely unlikely with random pivots).
• Space: $O(\log n)$ expected recursion depth.

Thus randomization makes the $O(n^2)$ worst case occur only with vanishing probability, giving robust $O(n\log n)$ expected performance.

Fractional Knapsack — Greedy Algorithm

Problem: Given $n$ items with weight $w_i$ and value $v_i$ and capacity $W$, choose fractions $x_i \in [0,1]$ of each item to maximize $\sum x_i v_i$ subject to $\sum x_i w_i \le W$.

Greedy choice: take items in decreasing order of value-to-weight ratio $v_i/w_i$; take whole items while they fit, then take a fraction of the next item to fill the remaining capacity.

FractionalKnapsack(w[1..n], v[1..n], W):
  compute ratio[i] = v[i]/w[i]
  sort items by ratio (descending)
  totalValue = 0
  for each item i in sorted order:
    if W >= w[i]:
      take whole item; W -= w[i]; totalValue += v[i]
    else:
      take fraction W/w[i]; totalValue += v[i] * (W / w[i]); W = 0; break
  return totalValue

Time Complexity

• Computing ratios: $O(n)$.
• Sorting by ratio: $O(n \log n)$ — the dominant cost.
• Greedy scan: $O(n)$.

Total: $\boxed{O(n \log n)}$.

Unlike 0/1 knapsack, the greedy strategy is optimal here because fractions are allowed (proved via an exchange argument).

Edit Distance: "ARTIFICIAL" → "NATURAL"

The edit (Levenshtein) distance is the minimum number of insertions, deletions and substitutions to transform one string into another.

Recurrence

Let $X$ = ARTIFICIAL (m=10), $Y$ = NATURAL (n=7). $D[i][j]$ = distance between first $i$ chars of $X$ and first $j$ chars of $Y$.

DP Table (rows = ARTIFICIAL, cols = NATURAL)

Result

Time complexity $O(mn)$, space $O(mn)$.

Dijkstra's Algorithm (Single-Source Shortest Path)

Finds shortest paths from a source $s$ to all vertices in a graph with non-negative edge weights. It is a greedy algorithm that repeatedly extracts the closest unfinalized vertex and relaxes its outgoing edges.

Dijkstra(G, s):
  for each vertex v: dist[v] = INF; prev[v] = NIL
  dist[s] = 0
  Q = min-priority queue of all vertices keyed by dist
  while Q not empty:
    u = Extract-Min(Q)
    for each edge (u, v) with weight w:
      if dist[u] + w < dist[v]:        // relaxation
        dist[v] = dist[u] + w
        prev[v] = u
        Decrease-Key(Q, v)

Example

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

• Init: dist A=0, others ∞. Extract A → relax: C=1, B=4.
• Extract C (1) → relax: B = min(4, 1+2)=3, D = 1+5=6.
• Extract B (3) → relax: D = min(6, 3+1)=4.
• Extract D (4) → done.

Shortest distances from A: A=0, C=1, B=3, D=4. Path to D: A→C→B→D.

Time Complexity

• With binary heap: $O((V+E)\log V)$.
• With Fibonacci heap: $O(E + V\log V)$.
• With simple array: $O(V^2)$.

Matrix Chain Multiplication

Problem: Given a chain of $n$ matrices $A_1, A_2, \ldots, A_n$ where $A_i$ has dimension $p_{i-1} \times p_i$, find the parenthesization that minimizes the number of scalar multiplications. Matrix multiplication is associative, so the result is the same but the cost differs greatly. Multiplying a $p\times q$ by $q\times r$ matrix costs $p\,q\,r$ scalar multiplications.

Dynamic Programming Formulation

Let $m[i][j]$ = minimum cost to compute the product $A_i A_{i+1} \cdots A_j$.

The index $k$ marks the split point of the optimal parenthesization; store it in $s[i][j]$ to reconstruct the parenthesization.

MatrixChainOrder(p[0..n]):
  for i = 1 to n: m[i][i] = 0
  for len = 2 to n:
    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
  return m[1][n]

Complexity

Three nested loops over $O(n)$ ranges → time $O(n^3)$, space $O(n^2)$. This exhibits optimal substructure and overlapping subproblems, the two hallmarks of dynamic programming.

Heap Sort

A comparison sort that uses a binary max-heap (a complete binary tree stored in an array where each parent $\ge$ its children). For node at index $i$: left child $= 2i$, right child $= 2i+1$, parent $= \lfloor i/2 \rfloor$.

Steps

1. Build a max-heap from the input array — $O(n)$.
2. Repeatedly: swap the root (maximum) with the last element, reduce heap size by 1, and Max-Heapify the root to restore the heap property — $n-1$ times.

HeapSort(A):
  BuildMaxHeap(A)
  for i = n down to 2:
    swap A[1], A[i]
    heapSize--
    MaxHeapify(A, 1)

MaxHeapify(A, i):     // sift down, O(log n)
  l=2i; r=2i+1; largest=i
  if l<=heapSize and A[l]>A[largest]: largest=l
  if r<=heapSize and A[r]>A[largest]: largest=r
  if largest != i: swap A[i],A[largest]; MaxHeapify(A, largest)

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

• Build max-heap → [10, 5, 3, 4, 1].
• Swap 10↔1, heapify → [5,4,3,1 | 10].
• Swap 5↔1, heapify → [4,1,3 | 5,10].
• Swap 4↔3, heapify → [3,1 | 4,5,10].
• Swap 3↔1 → [1 | 3,4,5,10].
• Sorted: [1, 3, 4, 5, 10].

Time Complexity

• BuildMaxHeap: $O(n)$.
• Each of $n-1$ heapify calls: $O(\log n)$.
• Total: $O(n \log n)$ in best, average and worst cases.
• In-place, space $O(1)$; not stable.