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

Asymptotic Notations

Asymptotic notations describe the growth rate of an algorithm's running time as input size $n \to \infty$.

• Big-O ($O$) — upper bound. $f(n) = O(g(n))$ if there exist constants $c>0, n_0>0$ such that $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$. (worst-case guarantee).
• Big-Omega ($\Omega$) — lower bound. $f(n) = \Omega(g(n))$ if $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$.
• Big-Theta ($\Theta$) — tight bound. $f(n) = \Theta(g(n))$ if $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$; i.e. $f$ is both $O(g)$ and $\Omega(g)$.

Master Theorem

For a recurrence of the form $T(n) = aT(n/b) + f(n)$ with $a \ge 1, b > 1$, compare $f(n)$ with $n^{\log_b a}$:

1. If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, then $T(n) = \Theta(n^{\log_b a})$.
2. If $f(n) = \Theta(n^{\log_b a})$, then $T(n) = \Theta(n^{\log_b a}\log n)$.
3. If $f(n) = \Omega(n^{\log_b a + \epsilon})$ and the regularity condition $a\,f(n/b) \le c\,f(n)$ holds for $c<1$, then $T(n) = \Theta(f(n))$.

Solving the Recurrences

(i) $T(n) = 3T(n/2) + n$

Here $a = 3, b = 2, f(n) = n$. Compute $n^{\log_b a} = n^{\log_2 3} \approx n^{1.585}$.

Since $f(n) = n = O(n^{\log_2 3 - \epsilon})$ (because $1 < 1.585$), Case 1 applies:

(ii) $T(n) = 2T(n/4) + \sqrt{n}$

Here $a = 2, b = 4, f(n) = \sqrt{n} = n^{1/2}$. Compute $n^{\log_b a} = n^{\log_4 2} = n^{1/2}$.

Since $f(n) = \Theta(n^{1/2}) = \Theta(n^{\log_4 2})$, Case 2 applies:

Complexity Classes

Class P (Polynomial time) — Set of decision problems solvable by a deterministic algorithm in polynomial time $O(n^k)$. These are the tractable problems. Examples: sorting, shortest path (Dijkstra), matrix multiplication, primality testing.

Class NP (Nondeterministic Polynomial time) — Set of decision problems whose yes-answer (a certificate/witness) can be verified in polynomial time by a deterministic algorithm. Equivalently, solvable in polynomial time by a nondeterministic machine. Examples: SAT, Hamiltonian cycle, subset-sum, vertex cover. Note $P \subseteq NP$; whether $P = NP$ is open.

NP-Hard — A problem $H$ is NP-Hard if every problem in NP reduces to it in polynomial time. NP-Hard problems are "at least as hard as the hardest problems in NP" but need not themselves be in NP (may not even be decision problems). Example: the optimization version of the Travelling Salesman Problem, Halting problem.

NP-Complete — A problem is NP-Complete if it is (i) in NP and (ii) NP-Hard. These are the hardest problems in NP. If any one NP-Complete problem is solved in polynomial time, then $P = NP$. Examples: CNF-SAT (Cook–Levin), 3-SAT, clique, vertex cover, Hamiltonian cycle.


Proving a Problem NP-Complete by Polynomial-Time Reduction

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

1. Show $X \in NP$ — give a polynomial-time verifier: a certificate that can be checked in poly time.
2. Show $X$ is NP-Hard — pick a known NP-Complete problem $Y$ and give a polynomial-time reduction $Y \le_p X$, i.e. a poly-time function $f$ that maps every instance $y$ of $Y$ to an instance $f(y)$ of $X$ such that

Because $Y$ is NP-Complete, every problem in NP reduces to $Y$, hence (by transitivity of reduction) to $X$, so $X$ is NP-Hard. Together with step 1, $X$ is NP-Complete.

Example: 3-SAT $\le_p$ Clique is used to prove Clique is NP-Complete.

0/1 Knapsack — Dynamic Programming

Given $n$ items with weights $w_i$ and values $v_i$, and capacity $W$, choose a subset (each item taken fully or not at all) maximizing total value without exceeding $W$.

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

Knapsack01(w, v, 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).

Solving for weights {2,3,4,5}, values {3,4,5,6}, W = 5

Items (1-indexed): item1 (w=2,v=3), item2 (w=3,v=4), item3 (w=4,v=5), item4 (w=5,v=6).

Key cell $K[2][5] = \max(K[1][5],\, 4 + K[1][2]) = \max(3,\, 4+3) = 7$.

Maximum value = $K[4][5] = 7$, achieved by selecting item 1 (w=2, v=3) and item 2 (w=3, v=4), total weight $2+3 = 5 \le W$.

BFS vs DFS

Time complexity (both): $O(V + E)$ with adjacency list; $O(V^2)$ with adjacency matrix.

Example — graph with edges A–B, A–C, B–D, C–D, starting at A:

• BFS order: A, B, C, D (expands A's neighbours first, then theirs).
• DFS order: A, B, D, C (goes A→B→D, backtracks, then C).

Applications: BFS — shortest path in unweighted graphs, peer-to-peer broadcasting; DFS — topological sorting, detecting cycles, finding connected/strongly-connected components.

Solving $T(n) = 2T(n/2) + n$

Recursion Tree Method

At each level the work splits into 2 subproblems of half the size; the non-recursive cost at the root is $n$.

• Level 0: cost $n$.
• Level 1: $2 \cdot (n/2) = n$.
• Level 2: $4 \cdot (n/4) = n$.
• Level $i$: $2^i \cdot (n/2^i) = n$.

The tree has height $\log_2 n$ (since size halves until it reaches 1), so there are $\log_2 n + 1$ levels, each contributing $n$ work:

Substitution Method

Guess: $T(n) = O(n \log n)$, i.e. $T(n) \le c\,n \log n$ for suitable $c$ and large $n$.

Inductive step: assume it holds for $n/2$:

This is $\le c\,n\log n$ provided $-cn + n \le 0$, i.e. $c \ge 1$. Hence the guess holds, and

(This is exactly the merge-sort recurrence.)

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 per unit, schedule a subset of jobs to maximize total profit such that each scheduled job finishes within its deadline.

Greedy Strategy

1. Sort jobs in decreasing order of profit.
2. Maintain a time-slot array of size = max deadline, initially all free.
3. For each job (highest profit first), place it in the latest free slot $\le$ its deadline. If no such slot is free, discard the job.

JobSequencing(jobs):
  sort jobs by profit descending
  maxDeadline = max(d_i); slot[1..maxDeadline] = free
  for each job j:
      for t = min(maxDeadline, d_j) downto 1:
          if slot[t] is free: assign j to t; break

Time complexity: $O(n^2)$ (or $O(n \log n)$ with a disjoint-set / priority-queue optimization).

Example

Sort by profit: B(100), A(60), D(40), C(20), E(20).

• B (d=1): slot 1 → B.
• A (d=2): slot 2 free → A.
• D (d=1): slot 1 taken → discard.
• C (d=2): slots 1,2 taken → discard.
• E (d=3): slot 3 free → E.

Schedule: slot1=B, slot2=A, slot3=E → jobs {B, A, E}, maximum profit = 100 + 60 + 20 = 180.

Naive String Matching

Slide the pattern $P$ of length $m$ over text $T$ of length $n$; at each of the $n-m+1$ positions, compare characters one by one.

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

• Time complexity: worst case $O((n-m+1)\,m) = O(nm)$ (e.g. $T = aaaa...$, $P = aaab$); best case $O(n)$.
• No preprocessing, $O(1)$ extra space.

Rabin–Karp Algorithm

Uses a rolling hash to compare the pattern's hash with the hash of each text window in $O(1)$ per shift; only on a hash match are characters compared to confirm (handle spurious hits / collisions).

Hash of window using base $d$ and prime modulus $q$:

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

• Time complexity: average / best case $O(n + m)$; worst case $O(nm)$ when many spurious hash collisions occur.
• Preprocessing $O(m)$; useful for multiple-pattern and 2-D matching.

Summary: Rabin–Karp matches naive's worst case but is typically much faster on average due to constant-time hash comparison.

Binary Search (Divide and Conquer)

Precondition: array $A$ is sorted. Repeatedly compare the key with the middle element and discard half the array.

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

Recurrence: $T(n) = T(n/2) + O(1)$, which by the master theorem (Case 2, $a=1, b=2, f(n)=\Theta(1)=\Theta(n^{\log_2 1})$) gives $T(n) = \Theta(\log n)$.

Complexity Analysis

• Best case: $O(1)$ — key is the middle element on the first comparison.
• Worst case: $O(\log_2 n)$ — key absent or at the deepest level; array is halved each step.
• Average case: $O(\log_2 n)$ — expected number of comparisons is $\approx \log_2 n - 1$.

Space: $O(\log n)$ recursive (call stack); $O(1)$ iterative.

Randomized Quicksort

Quicksort partitions the array around a pivot so that elements $<$ pivot lie left and elements $>$ pivot lie right, then recurses on each side. In randomized quicksort the pivot is chosen uniformly at random (or the array is randomly shuffled), which removes worst-case dependence on the input order.

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

Expected Time Complexity

Let $X$ be the total number of comparisons. For sorted elements $z_i, z_j$, let $X_{ij}=1$ if they are ever compared. They are compared iff one of them is the first pivot chosen from the set $\{z_i, \dots, z_j\}$, so

Then the expected number of comparisons is

Expected running time $= O(n\log n)$, independent of input order. The worst case is still $O(n^2)$ (all random pivots extreme), but it occurs with vanishingly small probability. Average extra space $O(\log n)$ for the recursion stack.

Fractional Knapsack — Greedy Algorithm

Unlike 0/1 knapsack, here a fraction of an item may be taken. The greedy choice of taking items in decreasing value-to-weight ratio $v_i / w_i$ is optimal.

FractionalKnapsack(items, W):
  for each item: ratio_i = v_i / w_i
  sort items by ratio descending
  totalValue = 0; cap = W
  for each item i (in sorted order):
      if w_i <= cap:
          take whole item; totalValue += v_i; cap -= w_i
      else:
          take fraction cap/w_i; totalValue += v_i * (cap / w_i); break
  return totalValue

Time Complexity

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

Total: $\Theta(n \log n)$.

Why greedy is optimal: taking the highest density first always fills capacity with the most value per unit weight; since items are divisible, the knapsack is filled exactly to capacity $W$ and an exchange argument shows no other selection can do better.

Edit Distance: "ARTIFICIAL" → "NATURAL"

Edit (Levenshtein) distance = minimum insertions, deletions, substitutions to convert one string to another. With $X$ of length $m$, $Y$ of length $n$:

Let $X =$ ARTIFICIAL ($m=10$), $Y =$ NATURAL ($n=7$).

Filling the $11 \times 8$ DP table (rows = ARTIFICIAL, cols = NATURAL):

Edit distance = $D[10][7] = 7$.

The two strings share the subsequence A, T, R, A, L; aligning these and editing the rest costs 7 operations. Time complexity: $O(mn)$.

Dijkstra's Single-Source Shortest Path Algorithm

Finds shortest paths from a source $s$ to all vertices in a graph with non-negative edge weights, using a greedy approach with a min-priority queue.

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

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

Example

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

1. Start: dist[A]=0, others $\infty$. Extract A; relax: dist[C]=1, dist[B]=4.
2. Extract C (1); relax C→B: $1+2=3 < 4$ ⇒ dist[B]=3; C→D: dist[D]=6.
3. Extract B (3); relax B→D: $3+1=4 < 6$ ⇒ dist[D]=4.
4. Extract D (4); done.

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

Note: Dijkstra fails with negative edge weights; use Bellman–Ford in that case.