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

Optimal Solution

An optimal solution is a feasible solution that gives the best possible value of the objective function for an optimization problem — the maximum (e.g., maximum profit) or minimum (e.g., minimum cost/length) among all feasible solutions. A feasible solution merely satisfies the constraints; an optimal one is feasible and best.

Does Greedy Always Guarantee Optimal?

No. A greedy algorithm builds a solution step by step, always making the locally best (greedy) choice in the hope of reaching a globally optimal solution. It is optimal only for problems that exhibit the:

• Greedy-choice property — a globally optimal solution can be reached by local optimal choices, and
• Optimal substructure — an optimal solution contains optimal solutions to subproblems.

When these hold, greedy is optimal (e.g., fractional knapsack, Huffman coding, Dijkstra, MST). When they do not, greedy can fail:

• 0/1 knapsack — greedy by value/weight ratio is not optimal.
• Coin change with arbitrary denominations (e.g., {1, 3, 4} for amount 6).

So greedy guarantees an optimal solution only for a restricted class of problems.

Huffman Tree for "SUPER DUPER CSIT"

Step 1 — Frequency count

String = SUPER DUPER CSIT (length 16, including 2 spaces).

Total = 2+2+2+2+2+2+1+1+1+1 = 16. ✓

Step 2 — Greedy merging (always merge the two smallest frequencies)

Use a min-priority queue. Repeatedly extract the two lowest-frequency nodes, merge them into a parent whose frequency is their sum, and reinsert.

1. Merge D(1) + C(1) → node DC(2)
2. Merge I(1) + T(1) → node IT(2)
3. Now all remaining = freq 2: {S,U,P,E,R,sp,DC,IT}. Merge S(2)+U(2) → SU(4)
4. Merge P(2)+E(2) → PE(4)
5. Merge R(2)+sp(2) → R_sp(4)
6. Merge DC(2)+IT(2) → DCIT(4)
7. Remaining freq-4 nodes {SU, PE, R_sp, DCIT}. Merge SU(4)+PE(4) → SUPE(8)
8. Merge R_sp(4)+DCIT(4) → R_sp_DCIT(8)
9. Merge SUPE(8)+R_sp_DCIT(8) → ROOT(16)

Step 3 — Huffman tree (assign 0 = left, 1 = right)

                 ROOT(16)
                /        \
            (0)            (1)
          SUPE(8)      R_sp_DCIT(8)
          /    \          /      \
       SU(4)  PE(4)   R_sp(4)   DCIT(4)
       / \    / \      /  \      /   \
      S   U  P   E    R   sp   DC(2) IT(2)
                                / \   / \
                               D   C I   T

Step 4 — Resulting Huffman codes

Step 5 — Cost

Encoded bits $= (2{+}2{+}2{+}2{+}2{+}2)\times 3 + (1{+}1{+}1{+}1)\times 4 = 36 + 16 = \mathbf{52}$ bits, versus $16 \times 4 = 64$ bits for fixed 4-bit codes — Huffman is more efficient.

(Codes may differ depending on tie-breaking order, but lengths and total cost stay the same.)

Order Statistics

The $i$-th order statistic of a set of $n$ elements is the element with rank $i$ — i.e., the $i$-th smallest element. Special cases:

• $i = 1$ → minimum
• $i = n$ → maximum
• $i = \lfloor (n+1)/2 \rfloor$ → median

The selection problem is to find the $i$-th order statistic of an unordered array. A trivial method sorts the array in $O(n\log n)$ then indexes position $i$. Better, the Randomized-Select algorithm (based on randomized partition) finds it in expected $O(n)$ time, and the deterministic median-of-medians algorithm achieves worst-case $O(n)$.

Randomized Quicksort

Quicksort sorts by partitioning an array around a pivot and recursing on both sides. In randomized quicksort, the pivot is chosen uniformly at random from the subarray, so the expected running time is independent of the input order and the deterministic $O(n^2)$ worst case (e.g., already-sorted input) is avoided with high probability.

RandomizedQuicksort(A, p, r):
  if p < r:
    q = RandomizedPartition(A, p, r)
    RandomizedQuicksort(A, p, q-1)
    RandomizedQuicksort(A, q+1, r)

RandomizedPartition(A, p, r):
  i = Random(p, r)        // random index in [p, r]
  swap A[i], A[r]         // move random pivot to end
  return Partition(A, p, r)

Partition(A, p, r):        // Lomuto partition
  x = A[r]                 // pivot
  i = p - 1
  for j = p to r-1:
    if A[j] <= x:
      i = i + 1
      swap A[i], A[j]
  swap A[i+1], A[r]
  return i + 1

Analysis

Partition cost: each Partition is $O(n)$.

Worst case: $O(n^2)$ — occurs only if every random pivot is the smallest/largest, which is extremely unlikely.

Best case: $O(n\log n)$ — pivot splits the array into two balanced halves: $T(n)=2T(n/2)+\Theta(n)=\Theta(n\log n)$.

Expected (average) case: Let $X$ = total number of comparisons. Two elements of ranks $z_i, z_j$ are compared at most once, with probability

$$P(z_i \text{ compared with } z_j) = \frac{2}{j-i+1}.$$

Then

$$E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \frac{2}{j-i+1} \le \sum_{i=1}^{n-1} 2 H_n = O(n\log n),$$

where $H_n$ is the $n$-th harmonic number. Hence the expected running time is $\Theta(n\log n)$.

• Space: $O(\log n)$ expected recursion-stack depth.
• Randomization guarantees $O(n\log n)$ expected time on every input, with the $O(n^2)$ case occurring with vanishing probability.

Dynamic Programming vs. Memoization

Both avoid recomputing overlapping subproblems, but differ in approach:

In short, memoization is the top-down, lazy form of dynamic programming, whereas classic DP (tabulation) is the bottom-up, eager form. Both run in the same asymptotic time when all subproblems are needed.

Matrix Chain Multiplication

(The four matrices are interpreted as a chain whose adjacent dimensions agree: A(30×1), B(1×40), C(40×10), D(10×15).)

Dimension array: $p = [p_0, p_1, p_2, p_3, p_4] = [30, 1, 40, 10, 15]$, so $A_1=30\times1,\;A_2=1\times40,\;A_3=40\times10,\;A_4=10\times15$.

Recurrence

$$m[i][j]=\begin{cases}0 & i=j\\ \displaystyle\min_{i\le k<j}\{m[i][k]+m[k+1][j]+p_{i-1}p_k p_j\} & i<j\end{cases}$$

Length-1 chains

$m[1][1]=m[2][2]=m[3][3]=m[4][4]=0.$

Length-2 chains

• $m[1][2]=p_0 p_1 p_2 = 30\cdot1\cdot40 = 1200$
• $m[2][3]=p_1 p_2 p_3 = 1\cdot40\cdot10 = 400$
• $m[3][4]=p_2 p_3 p_4 = 40\cdot10\cdot15 = 6000$

Length-3 chains

$m[1][3]=\min$:

• $k=1:\;m[1][1]+m[2][3]+p_0p_1p_3 = 0+400+30\cdot1\cdot10 = 700$
• $k=2:\;m[1][2]+m[3][3]+p_0p_2p_3 = 1200+0+30\cdot40\cdot10 = 13200$

→ $m[1][3]=\mathbf{700}$ (split at $k=1$).

$m[2][4]=\min$:

• $k=2:\;m[2][2]+m[3][4]+p_1p_2p_4 = 0+6000+1\cdot40\cdot15 = 6600$
• $k=3:\;m[2][3]+m[4][4]+p_1p_3p_4 = 400+0+1\cdot10\cdot15 = 550$

→ $m[2][4]=\mathbf{550}$ (split at $k=3$).

Length-4 chain (final)

$m[1][4]=\min$:

• $k=1:\;m[1][1]+m[2][4]+p_0p_1p_4 = 0+550+30\cdot1\cdot15 = 1000$
• $k=2:\;m[1][2]+m[3][4]+p_0p_2p_4 = 1200+6000+30\cdot40\cdot15 = 25200$
• $k=3:\;m[1][3]+m[4][4]+p_0p_3p_4 = 700+0+30\cdot10\cdot15 = 5200$

→ $m[1][4]=\mathbf{1000}$, optimal split at $k=1$.

Optimal Parenthesization

• $m[1][4]$ splits at $k=1$: $(A_1)(A_2A_3A_4)$
• $m[2][4]$ splits at $k=3$: $A_2A_3A_4 = (A_2A_3)(A_4)$

Optimal parenthesization: $\big(A\,(B\,C)\big)\,?$ — combining: $A_2A_3A_4 = ((A_2 A_3)A_4)$, then $A_1(\ldots)$ gives

$$\boxed{(A\,((B\,C)\,D))}$$

with minimum cost = 1000 scalar multiplications.

Solving T(n) = 2T(n/2) + n by Recursion Tree

Build the tree

Each node represents the non-recursive (combine/divide) cost at that call. The root has cost $n$ and two children of size $n/2$, each of cost $n/2$, and so on.

Level        Subproblems      Cost per node   Cost per level
  0 (root)        1                 n               n
  1               2               n/2          2·(n/2) = n
  2               4               n/4          4·(n/4) = n
  ...            ...              ...             ...
  i             2^i             n/2^i      2^i·(n/2^i) = n
  ...            ...              ...             ...
  last        n leaves          Θ(1)           Θ(n)

Cost per level

At level $i$ there are $2^i$ nodes, each costing $n/2^i$, so each level contributes exactly $n$.

Height of the tree

The subproblem size at level $i$ is $n/2^i$. Recursion stops when $n/2^i = 1 \Rightarrow i = \log_2 n$. So there are $\log_2 n + 1$ levels.

Total cost

$$T(n) = \sum_{i=0}^{\log_2 n} n = n\,(\log_2 n + 1) = n\log_2 n + n.$$

The leaf level contributes $\Theta(n)$, which is dominated by the $n\log n$ term.

$$\boxed{T(n) = \Theta(n\log n)}$$

(Verification by the Master Theorem: $a=2, b=2, f(n)=n$, $n^{\log_b a}=n^1=n=f(n)$ → case 2 → $\Theta(n\log n)$. ✓)

Bubble Sort — Best and Worst Case

Bubble sort repeatedly steps through the list, compares adjacent pairs, and swaps them if out of order; after each pass the largest remaining element "bubbles" to its place.

BubbleSort(A, n):
  for i = 1 to n-1:
    swapped = false
    for j = 1 to n-i:
      if A[j] > A[j+1]:
        swap A[j], A[j+1]
        swapped = true
    if not swapped: break      // optimization: array already sorted

Best Case

Occurs when the array is already sorted. With the swapped flag optimization, the first pass makes no swaps, so the algorithm stops after one pass.

• Comparisons: $n-1$, Swaps: $0$.
• Best-case time complexity = $O(n)$ (linear).

(Without the optimization, even the best case is $O(n^2)$.)

Worst Case

Occurs when the array is in reverse sorted order, so every comparison results in a swap.

• Pass $i$ does $n-i$ comparisons; total

$$\sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2} = O(n^2)$$

comparisons, and the same order of swaps.

• Worst-case time complexity = $O(n^2)$ (quadratic).

Summary

Space complexity $O(1)$ (in-place); bubble sort is stable.

Extended Euclidean Algorithm — GCD(12, 16)

The Extended Euclidean Algorithm computes $\gcd(a,b)$ and integers $x, y$ (Bézout coefficients) such that

$$a\cdot x + b\cdot y = \gcd(a,b).$$

We compute $\gcd(16, 12)$ (taking $a=16, b=12$).

Step 1 — Euclidean division (forward)

Last non-zero remainder = 4, so $\gcd(12, 16) = \mathbf{4}$.

Step 2 — Back-substitution (find x, y)

From step 1: $4 = 16 - 1\cdot12$.

So

$$16\cdot(1) + 12\cdot(-1) = 4 \quad\Rightarrow\quad x = 1,\; y = -1.$$

Verification

$16\cdot1 + 12\cdot(-1) = 16 - 12 = 4 = \gcd(12,16).$ ✓

Result

$$\boxed{\gcd(12, 16) = 4, \quad x = 1,\; y = -1}$$

(equivalently $\gcd = 4$ with $12\cdot(-1) + 16\cdot(1) = 4$).

Subset-Sum by Backtracking — target 21 in {5, 6, 10, 11, 15}

We seek all subsets whose elements sum to 21. Backtracking builds the subset incrementally: at each index we include or exclude the element, pruning a branch as soon as the partial sum exceeds the target.

Pruning rules

Let sum = current partial sum, remaining = sum of not-yet-considered elements.

• Prune if sum > 21 (overshoot).
• Prune if sum + remaining < 21 (can never reach target).
• Record the subset when sum == 21.

Backtrack(i, sum, chosen):
  if sum == 21: output chosen; return
  if i > n or sum > 21: return
  // include A[i]
  Backtrack(i+1, sum + A[i], chosen + A[i])
  // exclude A[i]
  Backtrack(i+1, sum, chosen)

State-space exploration (A = {5, 6, 10, 11, 15})

We look for combinations summing to 21:

• $5 + 6 + 10 = 21$ ✓
• $5 + 16?$ no single element 16.
• $6 + 15 = 21$ ✓
• $10 + 11 = 21$ ✓
• $5 + 6 + 10 = 21$ (already found); $5+11=16$, $6+10=16$, $5+15=20$, $11+10=21$ ✓ (same as above)
• Check 3-element: $5+6+10=21$ ✓; $5+6+11=22$ (prune); others overshoot.

Solution Subsets (sum = 21)

Three subsets of the array sum to 21: {5, 6, 10}, {6, 15}, and {10, 11}.

Worst-case time complexity of subset-sum backtracking is $O(2^n)$, but pruning prunes large portions of the search tree in practice.

Class P

Class P (Polynomial time) is the set of decision problems that can be solved by a deterministic algorithm in polynomial time $O(n^k)$ for some constant $k$. These are regarded as tractable / efficiently solvable. Examples: sorting, searching, shortest path, minimum spanning tree.

Class NP

Class NP (Nondeterministic Polynomial time) is the set of decision problems whose proposed solution (certificate) 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$; whether $P = NP$ is the famous open question.

Why Do We Need Approximation Algorithms? (Justification)

Many important problems are NP-Hard / NP-Complete, so no known algorithm solves them exactly in polynomial time, and (assuming $P \ne NP$) none exists. For large inputs, exact (exponential) methods are infeasible. Approximation algorithms address this by:

1. Running in polynomial time — practical even for large inputs.
2. Guaranteeing a provable bound on solution quality via an approximation ratio $\rho$, e.g., a result within factor $\rho$ of the optimum (a 2-approximation for vertex cover guarantees a cover at most twice the optimum).
3. Producing near-optimal solutions when an exact optimum is unnecessary or unaffordable.

Justification: For NP-Hard optimization problems (TSP, vertex cover, set cover, bin packing), we must trade a small, bounded loss in optimality for an enormous gain in running time. Approximation algorithms give the best practical compromise — fast, with quality guarantees — where exact algorithms are computationally hopeless.

Time and Space Complexity of Sequential (Linear) Search

Sequential search scans the array element by element until the target is found or the list ends.

SequentialSearch(A, n, key):
  for i = 1 to n:
    if A[i] == key: return i
  return -1

• Time complexity: $O(n)$ (worst and average), $O(1)$ best.
• Space complexity: $O(1)$ — only a constant amount of extra space (a loop index). Works on unsorted data.

Master Theorem (for divide-and-conquer recurrences)

For a recurrence of the form

$$T(n) = a\,T(n/b) + f(n), \qquad a \ge 1,\; b > 1,$$

compare $f(n)$ with the critical exponent $n^{\log_b a}$. Let $c = \log_b a$.

Examples: Merge sort $T(n)=2T(n/2)+n$ → case 2 → $\Theta(n\log n)$; Binary search $T(n)=T(n/2)+1$ → case 2 → $\Theta(\log n)$.

Worst Case of Binary Search — Justification

Binary search on a sorted array compares the target with the middle element and discards half the remaining elements each step.

• The search space halves every comparison: $n \to n/2 \to n/4 \to \cdots \to 1$.
• The worst case arises when the target is absent or found only at the deepest level, so the array must be halved until a single element remains.
• Number of halvings until size 1: $n/2^k = 1 \Rightarrow k = \log_2 n$.

The recurrence is $T(n) = T(n/2) + O(1)$, giving

$$\boxed{\text{Worst case} = O(\log n)}.$$

This is far better than linear search's $O(n)$, justifying binary search for sorted data.

Edit Distance: "RELEVANT" → "ELEPHANT"

Edit (Levenshtein) distance = minimum insertions, deletions, substitutions to transform one string into the other.

Recurrence

Let $X$ = RELEVANT (m=8), $Y$ = ELEPHANT (n=8). $D[i][j]$ = distance between first $i$ chars of $X$ and first $j$ of $Y$.

$$D[i][j]=\begin{cases}j & i=0\\ i & j=0\\ D[i-1][j-1] & X_i = Y_j\\ 1+\min(D[i-1][j],\,D[i][j-1],\,D[i-1][j-1]) & X_i \ne Y_j\end{cases}$$

DP Table (rows = RELEVANT, cols = ELEPHANT)

Result

$$\text{Edit Distance} = D[8][8] = \mathbf{3}.$$

Transformation: RELEVANT → ELEVANT (delete R) → ELEPANT (substitute V→P) → ELEPHANT (insert H) = 3 operations. Time $O(mn)$, space $O(mn)$.

Recursion vs. Backtracking

In short, all backtracking is recursive, but not all recursion is backtracking — backtracking adds the systematic try → check → undo search over a state-space tree.

Miller-Rabin Primality Test — Is 53 Prime?

The Miller-Rabin test checks primality of an odd $n$. Write $n-1 = 2^s \cdot d$ with $d$ odd. For a random base $a$, $n$ is probably prime if $a^d \equiv 1 \pmod n$ or $a^{2^r d} \equiv -1 \pmod n$ for some $0 \le r < s$.

Step 1 — Decompose $n - 1$

$n = 53$, so $n - 1 = 52 = 2^2 \cdot 13$. Thus $s = 2,\; d = 13$.

Step 2 — Choose a base, say $a = 2$

Compute $a^d \bmod n = 2^{13} \bmod 53$. $2^{13} = 8192$. $8192 \bmod 53$: $53\times154 = 8162$, $8192 - 8162 = 30$. So $2^{13} \equiv 30 \pmod{53}$.

• $30 \ne 1$ and $30 \ne 52\,(\equiv -1)$, so check the squaring sequence.

Step 3 — Square repeatedly (r = 1)

$2^{2d} = 30^2 = 900 \bmod 53$: $53\times16 = 848$, $900 - 848 = 52$.

$$2^{2\cdot13} \equiv 52 \equiv -1 \pmod{53}.$$

Since we found $a^{2^r d} \equiv -1 \pmod{53}$ (at $r = 1$), 53 passes the test for base 2.

Step 4 — Conclusion

53 passes Miller-Rabin (e.g., for base 2). Hence 53 is (probably) prime — and indeed 53 is a prime number.

0/1 Knapsack vs. Fractional Knapsack

The key difference: divisibility. Because fractional knapsack lets us fill the leftover capacity exactly using a fraction of the best-ratio item, the greedy choice is provably optimal (exchange argument). In 0/1 knapsack, indivisibility leaves "gaps" that greedy cannot fix, so DP is required.

Minimum Vertex Cover

A vertex cover is a set of vertices such that every edge has at least one endpoint in the set. The minimum vertex cover is the smallest such set. (Finding the exact minimum is NP-Hard in general; a standard 2-approximation repeatedly picks both endpoints of an uncovered edge.)

Approximation Algorithm (2-approximation)

ApproxVertexCover(G):
  C = {}
  E' = all edges of G
  while E' not empty:
    pick any edge (u, v) from E'
    add u and v to C
    remove from E' every edge incident on u or v
  return C

Example

Consider a graph with edges: (1-2), (1-3), (2-3), (3-4), (4-5).

• Pick edge (1-2): add {1, 2}; remove edges incident on 1 or 2 → removes (1-2),(1-3),(2-3). Remaining: (3-4),(4-5).
• Pick edge (3-4): add {3, 4}; remove (3-4),(4-5). Remaining: none.
• Cover returned = {1, 2, 3, 4} (size 4, a valid 2-approximation).

The true minimum vertex cover here is {1, 3, 4} (size 3): it covers (1-2) via 1, (1-3)/(2-3) via 1 and 3, (3-4) via 3/4, (4-5) via 4. Every edge is covered, so the minimum vertex cover size is 3.

(For an arbitrary graph supplied in the question, apply the same rule: select vertices until every edge is incident to a chosen vertex; the smallest such set is the minimum vertex cover.)