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

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 $\sum_{e\in T} w(e)$ is minimum among all spanning trees.

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm. It repeatedly picks the smallest-weight edge that does not form a cycle, using a disjoint-set (Union-Find) structure to detect cycles.

KRUSKAL(G):
    A = {}                      // edges of MST
    for each vertex v in V: MAKE-SET(v)
    sort edges of E in non-decreasing order of weight
    for each edge (u,v) in sorted order:
        if FIND-SET(u) != FIND-SET(v):   // adding edge does not form a cycle
            A = A union {(u,v)}
            UNION(u, v)
    return A

Example

Consider a graph with vertices $\{A,B,C,D,E\}$ and edges: $AB=1,\ BC=2,\ AC=3,\ CD=4,\ BD=5,\ DE=6,\ CE=7$.

Process edges in increasing order:

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

Complexity Analysis

• Sorting the $E$ edges: $O(E\log E)$.
• $V$ MAKE-SET and at most $2E$ FIND/UNION operations with union by rank + path compression: $O(E\,\alpha(V))$, nearly linear.
• Total: $O(E\log E)=O(E\log V)$ (since $E\le V^2$, $\log E=O(\log V)$).

Correctness follows from the greedy cut property: the lightest edge crossing any cut is safe to add to the MST.

Asymptotic Notations

Let $f(n),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$. (worst-case growth)
• Big-Omega (lower bound): $f(n)=\Omega(g(n))$ if $\exists c>0,n_0>0$ with $0\le c\,g(n)\le f(n)$ for all $n\ge n_0$. (best-case / lower growth)
• Big-Theta (tight bound): $f(n)=\Theta(g(n))$ if $f(n)=O(g(n))$ and $f(n)=\Omega(g(n))$, i.e. $\exists c_1,c_2,n_0$ with $c_1 g(n)\le f(n)\le c_2 g(n)$.

Master Theorem

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

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

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

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

Since $n = O(n^{c-\varepsilon})$ (because $1<1.585$), Case 1 applies:

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

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

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

Complexity Classes

• P (Polynomial time): Decision problems solvable by a deterministic algorithm in polynomial time $O(n^k)$. Examples: sorting, shortest path (Dijkstra), checking primality.
• NP (Nondeterministic Polynomial): Decision problems whose yes-answers can be verified in polynomial time given a certificate. Equivalently, solvable by a nondeterministic machine in polynomial time. Examples: SAT, Hamiltonian cycle, subset-sum. Note $P\subseteq NP$.
• 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 be in NP (and need not be decision problems). Example: the optimization Travelling Salesman Problem, the Halting problem.
• NP-Complete: A problem that is both in NP and NP-Hard. These are the hardest problems in NP. Examples: SAT (Cook–Levin theorem), 3-SAT, vertex cover, clique, Hamiltonian cycle.

Relationship: $P\subseteq NP$, $NPC = NP \cap NP\text{-Hard}$. Whether $P=NP$ is open.

Proving NP-Completeness via Polynomial-Time Reduction

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

1. Show $X\in NP$: give a polynomial-time verifier that checks a proposed certificate (solution).
2. Show $X$ is NP-Hard: pick a known NP-Complete problem $Y$ and construct a polynomial-time reduction $Y\le_p X$ — a transformation that maps any instance $y$ of $Y$ to an instance $f(y)$ of $X$ in polynomial time such that

3. Since $Y$ is NP-Complete, every NP problem reduces to $Y$ and hence (by transitivity of reductions) to $X$. Therefore $X$ is NP-Hard, and combined with step 1, $X$ is NP-Complete.

Example: 3-SAT $\le_p$ Clique shows Clique is NP-Hard; together with Clique $\in NP$ this proves Clique is NP-Complete.

Approximation Algorithms

For NP-Hard optimization problems exact optimal solutions cannot (assuming $P\ne NP$) be found in polynomial time. An approximation algorithm runs in polynomial time and returns a solution provably close to optimal. For a minimization problem it has approximation ratio $\rho$ if for every input $\frac{C}{C^*}\le \rho$, where $C$ is the cost returned and $C^*$ the optimal cost.

Approximation Algorithm for Vertex Cover

A vertex cover is a set of vertices covering every edge. Finding a minimum vertex cover is NP-Hard. A simple 2-approximation:

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

Why ratio 2: The edges picked in the loop form a matching $M$ (no two share a vertex). Any vertex cover must include at least one endpoint of each matched edge, so $|C^*|\ge |M|$. The algorithm adds both endpoints, so $|C|=2|M|\le 2|C^*|$. Hence it is a 2-approximation, running in $O(V+E)$ time.

Branch and Bound

Branch and Bound (B&B) is a systematic technique for solving optimization problems by exploring a state-space tree. It has two key operations:

• Branching: split a problem into smaller subproblems (children nodes).
• Bounding: compute a bound (lower bound for minimization) on the best solution obtainable in each subtree. If a node's bound is worse than the best solution found so far (the incumbent), the whole subtree is pruned, avoiding unnecessary exploration.

Unlike pure backtracking, B&B uses bounds to prune, and can use best-first / least-cost selection of the next node to expand.

Solving the Travelling Salesman Problem (TSP)

TSP asks for a minimum-cost tour visiting every city exactly once and returning to start.

1. State-space tree: each node represents a partial path; branching extends the path to an unvisited city.
2. Cost / lower bound: for each node compute a lower bound, commonly using the reduced cost matrix — reduce each row and column by its minimum; the sum of reductions plus the parent bound gives the node's lower bound on the completed tour cost.
3. Search: expand the live node with the smallest lower bound (least-cost B&B). Maintain the best complete tour found (incumbent / upper bound).
4. Pruning: discard any node whose lower bound $\ge$ current best tour cost.
5. Continue until the least-cost live node is a complete tour; that tour is optimal.

B&B does not improve worst-case complexity ($O(n!)$ in the worst case) but in practice prunes large portions of the search space, making moderate instances tractable.

BFS vs DFS

Both traverse a graph $G=(V,E)$ visiting every reachable vertex once.

• BFS explores level by level from a source, using a queue (FIFO). It first visits all neighbours, then their neighbours, finding shortest paths in unweighted graphs.
• DFS explores as deep as possible along a branch before backtracking, using a stack (LIFO) or recursion. Used for topological sort, cycle detection, connected components.

Example

Graph: $A$–$B$, $A$–$C$, $B$–$D$, $C$–$D$. Starting at $A$:

• BFS order: $A, B, C, D$ (visit $A$'s neighbours $B,C$ first, then $D$).
• DFS order: $A, B, D, C$ (go deep $A\to B\to D$, backtrack, then $C$).

Time Complexity

Using an adjacency list, both run in $O(V+E)$. With an adjacency matrix both are $O(V^2)$.

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

This is the merge-sort recurrence. We show $T(n)=\Theta(n\log n)$.

Substitution Method

Guess: $T(n)=O(n\log n)$, i.e. $T(n)\le c\,n\log n$ for some $c>0$.

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

This is $\le c\,n\log n$ provided $-cn+n\le 0$, i.e. $c\ge 1$. So the guess holds and $T(n)=O(n\log n)$. A symmetric argument gives $\Omega(n\log n)$, hence $T(n)=\Theta(n\log n)$.

Recursion Tree Method

At the root the cost is $n$. It splits into 2 subproblems of size $n/2$, each costing $n/2$, so level-1 cost $=2\cdot\tfrac{n}{2}=n$. In general at level $i$ there are $2^i$ nodes each of size $n/2^i$, contributing $2^i\cdot\tfrac{n}{2^i}=n$.

• Cost per level: $n$ (constant across levels).
• Number of levels: the size shrinks to 1 after $\log_2 n$ splits, so there are $\log_2 n + 1$ levels.

Total cost $=n\times(\log_2 n+1)=\Theta(n\log n)$.

Result: $T(n)=\Theta(n\log n)$ (confirmed by both methods; also matches Master Theorem Case 2 with $a=b=2$).

Job Sequencing with Deadlines

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. A job earns its profit only if completed by its deadline. Goal: schedule a subset of jobs to maximize total profit.

Greedy Approach

1. Sort jobs in decreasing order of profit.
2. Find the maximum deadline $D$; create $D$ time slots, all free.
3. For each job (highest profit first), place it in the latest free slot $\le$ its deadline. If no free slot exists, skip the job.
4. The filled slots give the schedule.

JOB-SEQUENCING(jobs):
    sort jobs by profit descending
    D = max deadline; slot[1..D] = free
    for each job j:
        for t = min(D, j.deadline) down to 1:
            if slot[t] is free:
                slot[t] = j; break
    return filled slots

Example

Sorted by profit: A,B,C,D,E. Max deadline $=3$, slots $[\_,\_,\_]$.

• A (d=2) → slot 2: $[\_,A,\_]$
• B (d=2) → slot 1 (2 taken): $[B,A,\_]$
• C (d=1) → slot 1 taken, skip.
• D (d=3) → slot 3: $[B,A,D]$
• E (d=3) → all $\le 3$ taken, skip.

Schedule: B → A → D, maximum profit $=15+20+5=40$.

Complexity: $O(n\log n)$ for sorting plus $O(n\cdot D)$ for slot assignment (improvable to near $O(n\log n)$ with a disjoint-set structure).

Naive String Matching

To find a pattern $P$ of length $m$ in text $T$ of length $n$, the naive algorithm slides $P$ over every position $s=0,\dots,n-m$ and checks character by character.

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

• Time: $O((n-m+1)\,m)=O(nm)$ in the worst case (e.g. $T=aaaa\ldots$, $P=aaab$). No preprocessing.

Rabin–Karp Algorithm

Rabin–Karp uses hashing. It computes a hash of the pattern and of each length-$m$ window of the text; only when hashes match does it compare characters (to rule out spurious hits).

1. Compute hash $h(P)$ of the pattern.
2. Compute hash of $T[0..m-1]$.
3. Slide the window: update the hash in $O(1)$ using a rolling hash

where $d$ is the alphabet size and $q$ a large prime. 4. When $h_s = h(P)$, verify the actual characters to confirm.

• Time: Preprocessing $O(m)$; matching $O(n+m)$ on average (with a good hash and few collisions), but $O(nm)$ in the worst case when many spurious hash collisions force full comparisons.

Summary: both report all occurrences; Rabin–Karp is typically faster in practice and naturally extends to multi-pattern and 2-D matching.

Binary Search (Divide and Conquer)

Binary search finds a key $x$ in a sorted array $A[low..high]$ by repeatedly comparing with the middle element and discarding half the array.

BINARY-SEARCH(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 BINARY-SEARCH(A, low, mid - 1, x)   // search left half
    else:
        return BINARY-SEARCH(A, mid + 1, high, x)  // search right half

The recurrence is $T(n)=T(n/2)+O(1)$, which by the Master Theorem (Case 2 with $a=1,b=2$) gives $T(n)=\Theta(\log n)$.

Complexity Analysis

• Best case: key is the middle element on the first comparison → $O(1)$.
• Worst case: key absent or at the deepest level; the array halves each step, so $\lfloor\log_2 n\rfloor + 1$ comparisons → $O(\log n)$.
• Average case: also $O(\log n)$ (the search tree has depth $\log n$, so expected comparisons $\approx \log_2 n - 1$).
• Space: $O(\log n)$ for the recursion stack, or $O(1)$ if written iteratively.

Randomized Quicksort

Quicksort sorts by choosing a pivot, partitioning the array so that elements smaller than the pivot go left and larger go right, then recursively sorting the two parts. Standard quicksort degrades to $O(n^2)$ when the pivot is consistently the smallest/largest (e.g. already-sorted input).

Randomized quicksort avoids this by choosing the pivot uniformly at random from the subarray, so no particular input triggers worst-case behaviour.

RANDOMIZED-QUICKSORT(A, p, r):
    if p < r:
        i = RANDOM(p, r)          // random index
        swap A[i] with A[r]       // random pivot
        q = PARTITION(A, p, r)    // O(n) partition around pivot
        RANDOMIZED-QUICKSORT(A, p, q - 1)
        RANDOMIZED-QUICKSORT(A, q + 1, r)

Expected Time Complexity

Let $X$ be the total number of comparisons. Define indicator $X_{ij}=1$ if elements of ranks $i$ and $j$ are ever compared. Two elements are compared iff one of them is chosen as pivot before any element ranked between them, which happens with probability $\frac{2}{j-i+1}$. Thus

Therefore the expected running time is $\Theta(n\log n)$, independent of the input ordering. The worst case is still $O(n^2)$ but occurs only with negligibly small probability.

Fractional Knapsack Problem

Given $n$ items each with weight $w_i$ and value $v_i$, and a knapsack 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$. Because items can be divided, a greedy strategy by value-to-weight ratio gives the optimal solution.

Greedy Algorithm

1. Compute the ratio $v_i/w_i$ for each item.
2. Sort items in decreasing order of $v_i/w_i$.
3. Take items fully in that order until the next item does not fit; take a fraction of that item to fill the remaining capacity exactly.

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

Optimality: the exchange argument shows replacing any part of a lower-ratio item with a higher-ratio one never decreases value, so the greedy choice is optimal.

Time Complexity

• Sorting by ratio: $O(n\log n)$.
• Single greedy pass: $O(n)$.
• Total: $O(n\log n)$, dominated by sorting.