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

Backtracking

Backtracking is an algorithmic technique for solving problems incrementally by building a solution one piece at a time and abandoning a partial candidate ("backtracking") as soon as it determines the candidate cannot possibly lead to a valid complete solution. It performs a systematic depth-first search of the state-space tree, using bounding/feasibility checks to prune branches that violate constraints.

Backtracking vs. Recursion

In short, backtracking is recursion + state-space search + pruning.

4-Queens Problem using Backtracking

Place 4 queens on a $4\times4$ board so that no two attack each other (no two in the same row, column, or diagonal). We place one queen per row and try columns $1..4$, backtracking when a placement is unsafe.

A placement at row $i$, column $j$ is safe w.r.t. an earlier queen at $(k, c)$ if:

algorithm NQueens(board, row, n):
    if row == n:
        output solution; return
    for col = 0 to n-1:
        if isSafe(board, row, col):
            place queen at (row, col)
            NQueens(board, row+1, n)
            remove queen from (row, col)   // backtrack

Trace for n = 4 (board[row] = column):

• Row 0: place Q at col 0.
• Row 1: col 0,1 unsafe → col 2 safe. Place at col 2.
• Row 2: cols 0,1,2,3 all attacked → dead end, backtrack to row 1.
• Row 1: try col 3. Place at col 3.
• Row 2: only col 1 safe. Place at col 1.
• Row 3: col 0,1,2 unsafe, col 3 unsafe → dead end. Backtrack repeatedly to row 0.
• Row 0: place Q at col 1.
• Row 1: col 3 safe. Row 2: col 0 safe. Row 3: col 2 safe. Solution found.

Solution: positions $(0,1),(1,3),(2,0),(3,2)$:

. Q . .
. . . Q
Q . . .
. . Q .

(The second solution is its mirror: $(0,2),(1,0),(2,3),(3,1)$.)

Time Complexity

Without pruning, $n$ queens in $n$ rows with $n$ column choices gives an upper bound of $O(n^n)$; restricting to one queen per column gives $O(n!)$ permutations. Each isSafe check costs $O(n)$, so a loose bound is $O(n! \cdot n)$. Backtracking's pruning dramatically reduces the explored nodes in practice, but the worst-case time complexity remains exponential, $O(n!)$.

Minimum Spanning Tree (MST)

Given a connected, undirected, weighted graph $G=(V,E)$, a spanning tree is a subgraph that is a tree connecting all $|V|$ vertices using exactly $|V|-1$ edges. A Minimum Spanning Tree is a spanning tree whose total edge weight is the minimum among all spanning trees of $G$.

Kruskal's Algorithm

Kruskal's is a greedy algorithm that builds the MST by repeatedly adding the smallest-weight edge that does not form a cycle, using a Disjoint-Set (Union-Find) structure to detect cycles.

algorithm Kruskal(G):
    A = {}                      // MST edge set
    for each vertex v: MakeSet(v)
    sort all edges E in non-decreasing order of weight
    for each edge (u, v) in sorted order:
        if Find(u) != Find(v):  // u, v in different components -> no cycle
            A = A union {(u,v)}
            Union(u, v)
    return A

Example

Graph with vertices $\{A,B,C,D\}$ and edges: $AB=1,\; BC=2,\; CD=3,\; AD=4,\; AC=5$.

Sort edges: $AB(1), BC(2), CD(3), AD(4), AC(5)$.

MST edges = $\{AB, BC, CD\}$, total weight $= 1+2+3 = 6$, with $|V|-1 = 3$ edges.

Complexity Analysis

• Sorting $E$ edges: $O(E \log E)$.
• Union-Find operations (with union by rank + path compression): nearly $O(E\,\alpha(V))$, effectively $O(E)$.

Overall: $O(E \log E) = O(E \log V)$ time (since $E \le V^2$, $\log E = O(\log V)$). Space: $O(V+E)$.

Asymptotic Notations

Let $f(n)$ and $g(n)$ be non-negative functions.

• Big-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$. It gives the worst-case / upper growth rate.
• Big-Omega (Lower bound): $f(n)=\Omega(g(n))$ if there exist $c>0, n_0>0$ such that $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$. It gives a lower bound.
• Big-Theta (Tight bound): $f(n)=\Theta(g(n))$ if there exist $c_1,c_2>0, n_0>0$ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$. Thus $f=\Theta(g)$ iff $f=O(g)$ and $f=\Omega(g)$.

Master Theorem

For a recurrence of the form $T(n)=aT(n/b)+f(n)$ with $a\ge1, b>1$, let $c = \log_b a$. Compare $f(n)$ with $n^{c}$:

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

Recurrence 1: $T(n)=3T(n/2)+n$

Here $a=3, b=2, f(n)=n$. $\;c=\log_2 3 \approx 1.585$.

Compare $f(n)=n=n^1$ with $n^{1.585}$. Since $n = O(n^{\,c-\epsilon})$ (e.g. $\epsilon\approx0.585$), Case 1 applies.

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

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

Compare $f(n)=n^{1/2}$ with $n^{c}=n^{1/2}$. They are equal, so $f(n)=\Theta(n^{c})$ — Case 2 applies.

Heap Sort

Heap sort is a comparison-based sorting algorithm that uses a binary max-heap (a complete binary tree where every parent $\ge$ its children, stored in an array).

Steps:

1. Build a max-heap from the input array (heapify from the last internal node down to the root).
2. Repeatedly extract the maximum: swap the root (largest) with the last element, reduce heap size by 1, and call max-heapify on the root to restore the heap property.
3. Repeat until the heap is empty; the array becomes sorted in ascending order.

HeapSort(A, n):
    BuildMaxHeap(A, n)
    for i = n-1 downto 1:
        swap(A[0], A[i])
        MaxHeapify(A, 0, i)   // heap size = i

Example

Sort $A=[4,10,3,5,1]$.

• Build max-heap: $[10,5,3,4,1]$.
• Swap root 10 with last → $[1,5,3,4 \,|\,10]$, heapify → $[5,4,3,1\,|\,10]$.
• Swap 5 → $[1,4,3\,|\,5,10]$, heapify → $[4,1,3\,|\,5,10]$.
• Swap 4 → $[3,1\,|\,4,5,10]$, heapify → $[3,1\,|\,4,5,10]$.
• Swap 3 → $[1\,|\,3,4,5,10]$.
• Sorted: $[1,3,4,5,10]$.

Time Complexity

• BuildMaxHeap: $O(n)$.
• Each of the $n-1$ extractions calls MaxHeapify costing $O(\log n)$ → $O(n\log n)$.

Total: $O(n\log n)$ in best, average and worst cases. It sorts in place ($O(1)$ extra space) but is not stable.

Subset-Sum Problem

Given a set of positive integers $S=\{s_1,s_2,\dots,s_n\}$ and a target sum $W$, find a subset whose elements add up to exactly $W$.

Backtracking Approach

We explore a binary state-space tree: at each element we decide to include or exclude it. We track the running sum and prune branches using two bounding conditions (assuming elements are sorted):

• Prune if currentSum + s[i] > W (including this element overshoots), and
• Prune if currentSum + (sum of remaining elements) < W (cannot reach $W$).

SubsetSum(i, currentSum, subset):
    if currentSum == W: output subset; return
    if i == n or currentSum > W: return
    // include s[i]
    if currentSum + s[i] <= W:
        SubsetSum(i+1, currentSum + s[i], subset + s[i])
    // exclude s[i]
    if currentSum + remainingSum(i+1) >= W:
        SubsetSum(i+1, currentSum, subset)

Example

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

• Include 3 → sum 3. Include 4 → 7. Include 5 → 12 (>9, prune). Exclude 5, include 6 → 13? no; from 7 exclude 5,exclude... reaching dead ends.
• From sum 3, exclude 4, include 5 → 8, include 6 → 14 prune; exclude 6 → dead end.
• Include 3, exclude 4, exclude 5, exclude 6 → 3 ≠ 9.
• Backtrack: exclude 3, include 4, include 5 → 9 ✓ → subset $\{4,5\}$.
• Also include 3, include 6 → 9 ✓ → subset $\{3,6\}$.

Solutions: $\{4,5\}$ and $\{3,6\}$.

Complexity

The worst-case state space has $2^n$ nodes, so the time complexity is $O(2^n)$, though pruning reduces the search substantially in practice.

Approximation Algorithms

Many optimization problems (e.g. vertex cover, TSP) are NP-hard, so no known polynomial-time algorithm finds the exact optimum. An approximation algorithm runs in polynomial time and returns a solution guaranteed to be within a provable factor of the optimum.

For a minimization problem, an algorithm has approximation ratio $\rho$ if for every input the cost $C$ of its solution satisfies $C \le \rho \cdot C^{*}$, where $C^{*}$ is the optimal cost.

Approximation Algorithm for Vertex Cover

A vertex cover of graph $G=(V,E)$ is a set of vertices that includes at least one endpoint of every edge. Finding the minimum vertex cover is NP-hard. The following greedy algorithm gives a 2-approximation:

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

Why it is a 2-approximation

The set of edges picked in the loop forms a matching $M$ (they share no endpoints). Any vertex cover must include at least one endpoint of each edge in $M$, so $|C^{*}| \ge |M|$. The algorithm adds both endpoints, so $|C| = 2|M| \le 2|C^{*}|$.

Thus $|C| \le 2\,|C^{*}|$ — the solution is at most twice the optimum. Running time is $O(V+E)$.

Example: for a path $a-b-c$, picking edge $(a,b)$ adds $\{a,b\}$ and covers both edges → cover $\{a,b\}$ (size 2 vs optimum $\{b\}$ of size 1, still within factor 2).

Branch and Bound

Branch and Bound (B&B) is a technique for solving optimization problems (often NP-hard) by systematically exploring the state-space tree while using bounds to prune subtrees that cannot contain an optimal solution.

• Branch: partition the problem into subproblems (children of a node).
• Bound: compute a lower bound (for minimization) on the best solution obtainable in each subtree.
• Prune: if a node's bound $\ge$ the cost of the best complete solution found so far, discard that subtree.

Nodes are explored using strategies such as least-cost (best-first), FIFO (BFS), or LIFO (DFS). Unlike pure backtracking (which only checks feasibility), B&B uses a cost/bound function to guide and prune the search.

Travelling Salesman Problem (TSP) with B&B

TSP: find the minimum-cost tour that visits every city exactly once and returns to the start.

Lower-bound function: A common bound is computed from the reduced cost matrix. For each row and column, subtract its minimum entry; the sum of all subtracted values is a lower bound on any tour cost.

Procedure:

1. Form the cost matrix; reduce it (row + column reduction) to get the root's lower bound.
2. Branch by choosing to include or exclude a particular edge $(i,j)$, creating child nodes.
3. For each child, set the chosen row $i$ / column $j$ (and the reverse edge) to $\infty$, re-reduce the matrix, and add the reduction cost + edge cost to the parent's bound to get the child's bound.
4. Use a priority queue to always expand the live node with the least bound (best-first search).
5. When a complete tour is reached, update the best (upper bound). Prune any node whose lower bound $\ge$ current best.
6. Continue until the least-bound live node is itself a complete tour → optimal.

B&B avoids exploring the full $O(n!)$ search space by pruning, though its worst-case time is still exponential. It guarantees the exact optimal tour.

BFS vs. DFS

Both Breadth First Search (BFS) and Depth First Search (DFS) are graph traversal algorithms that visit every vertex once.

Time Complexity

For a graph with $V$ vertices and $E$ edges using an adjacency list, both run in $O(V+E)$. With an adjacency matrix, both run in $O(V^2)$.

Example

Graph (adjacency): $A\!:\!B,C\;\;B\!:\!D,E\;\;C\!:\!F\;\;D,E,F\!:\!-$, starting at $A$.

• BFS order: $A, B, C, D, E, F$ (explores neighbours level by level).
• DFS order: $A, B, D, E, C, F$ (goes deep along $A\to B\to D$, backtracks, then $C\to F$).

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

This is the recurrence for merge sort. We solve it two ways.

(a) Substitution Method

Guess: $T(n)=O(n\log n)$. Prove $T(n)\le c\,n\log n$ by induction.

Assume it holds for $n/2$: $T(n/2)\le c\,\frac{n}{2}\log\frac{n}{2}$. Then

With $\log 2 = 1$:

The inductive step holds, so $T(n)=O(n\log n)$.

(b) Recursion Tree Method

At each level the work done equals the sum of the non-recursive terms:

Each level contributes $n$ work. The tree has height $\log_2 n$, so there are $\log_2 n + 1$ levels.

Conclusion: $\boxed{T(n)=\Theta(n\log n)}$ (confirmed by both methods; also Master Theorem Case 2).

Job Sequencing with Deadlines

Problem: Given $n$ jobs, each with a deadline $d_i$ and a profit $p_i$ (earned only if the job finishes by its deadline), schedule jobs on a single machine where each job takes one unit of time. Maximize total profit. Only one job runs per time slot.

Greedy Approach

1. Sort all jobs in decreasing order of profit.
2. Find the maximum deadline $d_{max}$ and create that many time slots (initially empty).
3. For each job (highest profit first), place it in the latest free slot at or before its deadline. If no such slot is free, reject the job.

JobSequencing(jobs):
    sort jobs by profit descending
    slots[1..dmax] = free
    for each job j:
        for t = min(dmax, j.deadline) downto 1:
            if slots[t] is free:
                slots[t] = j; break

Example

Max deadline = 3, so slots [1][2][3].

• J1 (p20, d2): place at slot 2 → [_, J1, _].
• J2 (p15, d2): slot 2 full → slot 1 → [J2, J1, _].
• J3 (p10, d1): slot 1 full → rejected.
• J4 (p5, d3): slot 3 free → [J2, J1, J4].
• J5 (p1, d3): slots 3,2,1 full → rejected.

Schedule: J2 → J1 → J4. Maximum profit $= 15+20+5 = 40$.

Complexity

Sorting is $O(n\log n)$; slot assignment is $O(n\cdot d_{max})$, so overall $O(n^2)$ in the simple version (or near $O(n\log n)$ with a disjoint-set optimization).

Naive String Matching

To find a pattern $P$ of length $m$ in a text $T$ of length $n$, the naive algorithm slides $P$ over $T$ one position at a time and, at each of the $n-m+1$ shifts, compares characters one by one.

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

• Best case: $O(n)$ (mismatch on first character each time).
• Worst case: $O((n-m+1)\cdot m) = O(nm)$ (e.g. $T=\texttt{aaaa...a}$, $P=\texttt{aaab}$).

Rabin-Karp Algorithm

Rabin-Karp uses hashing to avoid comparing every character at every shift. It computes a hash of the pattern and a rolling hash of each $m$-length window of the text; only when hashes match does it verify character by character (to handle collisions / spurious hits).

The rolling hash updates in $O(1)$ per shift:

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

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

Time Complexity

With a good hash and prime $q$, Rabin-Karp runs in $O(n+m)$ on average; its worst case degrades to $O(nm)$ when spurious hits force full verification.

Binary Search (Divide and Conquer)

Binary search finds a key $x$ in a sorted array $A[\,low..high\,]$ by repeatedly comparing $x$ with the middle element and discarding half the array each time — a classic divide-and-conquer technique.

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

Each step reduces the problem size to $n/2$, giving the recurrence:

By the Master Theorem ($a=1, b=2, c=\log_2 1 = 0$, $f(n)=O(1)=\Theta(n^0)$, Case 2): $T(n)=\Theta(\log n)$.

Time Complexity Analysis

Space: $O(\log n)$ for the recursive call stack ($O(1)$ if implemented iteratively).