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

Greedy Method

The greedy method builds a solution piece by piece, always choosing the option that looks best (locally optimal) at the current step, without reconsidering earlier choices. It works correctly only when the problem has the greedy-choice property (a global optimum can be reached by local choices) and optimal substructure.

General structure:

Greedy(C):              // C = set of candidates
  S = {}                 // solution
  while C != {} and not solution(S):
     x = select(C)       // best candidate by greedy criterion
     C = C - {x}
     if feasible(S + x): S = S + x
  return S

Examples: Huffman coding, Kruskal/Prim MST, Dijkstra, fractional knapsack, job sequencing.

Huffman Code for "CYBER CRIME"

String = CYBER CRIME (length 11 including the space). Frequencies:

Total = 11. Build the Huffman tree by repeatedly merging the two lowest-frequency nodes.

1. Merge Y(1)+B(1) → 2
2. Merge ' '(1)+I(1) → 2
3. Merge M(1) with C(2) → 3
4. Merge R(2)+E(2) → 4
5. Merge (Y B)=2 + ( I)=2 → 4
6. Merge (M C)=3 + (R E)=4 → 7
7. Merge (YB I)=4 + (M C R E)=7 → 11 (root)

A valid set of resulting prefix codes (depths give code lengths):

Total bits $= \sum f_i \cdot \text{len}_i = 6+6+6+6+4+4+4+4 = 40$ bits.

With a fixed 8-symbol alphabet, naive fixed-length coding needs $\lceil \log_2 8\rceil = 3$ bits/symbol $\times 11 = 33$ bits; Huffman is optimal for the given frequency distribution and here yields 40 bits for the full string (codes are prefix-free, so no separator is needed). Average code length $= 40/11 \approx 3.64$ bits/symbol.

Note: Several tie-break orderings give equally optimal trees; the total weighted bit count for these frequencies is the same.

Backtracking

Backtracking is an algorithmic technique that incrementally builds candidates to a solution and abandons a candidate ("backtracks") as soon as it determines the candidate cannot lead to a valid solution. It performs a depth-first traversal of an implicit state-space tree, pruning branches that violate constraints.

Backtracking vs Recursion

So backtracking is a strategy built on recursion plus pruning; not every recursion is backtracking.

4-Queens Problem

Place 4 queens on a 4×4 board so that no two share a row, column, or diagonal. Place one queen per row; for row $i$ choose column $j$ such that it is safe: no earlier queen in same column or on diagonals ($|i-i'| \ne |j-j'|$).

Search (rows top to bottom):

• Row1: col1 → conflicts cascade, backtrack.
• Try Row1=col2:
  • Row2: col4 (safe).
  • Row3: col1 (safe).
  • Row4: col3 (safe). ✓ Solution found.

One solution: (Row1,Col2), (Row2,Col4), (Row3,Col1), (Row4,Col3).

Board (Q = queen):

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

The second solution is its mirror: (Col3, Col1, Col4, Col2).

Algorithm

NQueens(board, row, n):
  if row == n: report 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 (backtrack)

Time Complexity

Without pruning the upper bound is $O(n^n)$; a queen per row reduces it to $O(n!)$ (each row tries up to $n$ columns, then $n-1$, etc.). The constraint checks prune most branches, so practical performance is far better, but the worst-case is $O(n!)$. For $n=4$ the tree is tiny and solved quickly.

Minimum Spanning Tree (MST)

For 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 w(e)$ is minimum among all spanning trees.

Kruskal's Algorithm

Kruskal grows the MST by adding edges in increasing weight order, skipping any edge that would form a cycle (detected with a Disjoint-Set / Union-Find structure).

Kruskal(G):
  A = {}                       // MST edge set
  for each vertex v: MakeSet(v)
  sort edges E by weight ascending
  for each edge (u,v) in sorted order:
     if Find(u) != Find(v):    // no cycle
        A = A + {(u,v)}
        Union(u,v)
  return A

Example

Graph with edges: A-B=1, A-C=3, B-C=3, B-D=6, C-D=4, C-E=2, D-E=5.

Sort: A-B(1), C-E(2), A-C(3), B-C(3), C-D(4), D-E(5), B-D(6).

Process:

1. A-B(1) → add. Sets: {A,B}
2. C-E(2) → add. {C,E}, {A,B}
3. A-C(3) → add (joins the two sets). {A,B,C,E}
4. B-C(3) → both in same set → skip (cycle)
5. C-D(4) → add. {A,B,C,D,E} — all 5 vertices, 4 edges done.

MST edges: A-B, C-E, A-C, C-D with total weight $1+2+3+4 = 10$.

Complexity Analysis

• Sorting edges: $O(E \log E)$.
• Union-Find operations over $E$ edges with path compression + union by rank: $O(E\,\alpha(V))$, nearly linear.
• Overall: $O(E \log E) = O(E \log V)$ (since $E \le V^2$, $\log E = O(\log V)$). This dominates the runtime.

Dijkstra's Algorithm (Single-Source Shortest Path)

Finds shortest path distances from a source $s$ to all vertices in a graph with non-negative edge weights, using a greedy approach.

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

Example

Graph (directed/undirected), source = A: A-B=4, A-C=1, C-B=2, C-D=5, B-D=1.

Shortest distances: A→A=0, A→B=3 (A-C-B), A→C=1, A→D=4 (A-C-B-D).

Complexity

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

Matrix Chain Multiplication

Given a chain of 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 fixed, but the cost depends on the order: multiplying a $p \times q$ and $q \times r$ matrix costs $p \cdot q \cdot r$ scalar multiplications.

The number of parenthesizations grows like the Catalan numbers (exponential), so brute force is infeasible — hence dynamic programming.

DP Formulation

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

• Base case: $m[i][i] = 0$ (single matrix, no multiplication).
• Recurrence: for $i < j$,

The index $k$ is the split point; we store $s[i][j]=k$ to reconstruct the optimal parenthesization.

MatrixChainOrder(p[0..n]):
  for i = 1 to n: m[i][i] = 0
  for L = 2 to n:                 // chain length
    for i = 1 to n-L+1:
      j = i+L-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)$ each: time $O(n^3)$, space $O(n^2)$. The answer is $m[1][n]$.

Heap Sort

Heap sort uses a binary max-heap (a complete binary tree stored in an array where every parent ≥ its children). It has two phases:

1. Build max-heap from the input array.
2. Repeatedly extract the max (swap root with last element, shrink heap, sift down) to place elements in sorted order.

Array indexing (0-based): for node $i$, children are $2i+1$ and $2i+2$, parent is $\lfloor (i-1)/2 \rfloor$.

HeapSort(A, n):
  for i = n/2 - 1 downto 0: Heapify(A, n, i)   // build max-heap
  for i = n-1 downto 1:
     swap(A[0], A[i])      // largest to its final position
     Heapify(A, i, 0)      // restore heap on reduced size

Heapify(A, n, i):
  largest = i; l = 2i+1; r = 2i+2
  if l<n and A[l]>A[largest]: largest = l
  if r<n and A[r]>A[largest]: largest = r
  if largest != i: swap(A[i],A[largest]); Heapify(A,n,largest)

Example

Sort [4, 10, 3, 5, 1].

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

Sorted: [1, 3, 4, 5, 10].

Time Complexity

• Build-heap: $O(n)$.
• $n-1$ extractions, each $O(\log n)$: $O(n \log n)$.
• Best, average, and worst case: $O(n \log n)$. In-place, space $O(1)$; not stable.

Subset-Sum via Backtracking

Problem: Given a set of positive integers $S = \{w_1, w_2, \ldots, w_n\}$ and a target $T$, find a subset whose elements sum exactly to $T$.

Backtracking idea: Build a binary state-space tree — at each element $w_i$ decide to include it or exclude it. Prune a branch when:

• current sum exceeds $T$ (overshoot), or
• current sum + sum of remaining elements < $T$ (can never reach target).

Elements are usually sorted ascending to make bounding effective.

SubsetSum(i, currSum, remaining):
  if currSum == T: report solution; return
  if i == n or currSum > T or currSum + remaining < T: return  // prune
  // include w[i]
  SubsetSum(i+1, currSum + w[i], remaining - w[i])
  // exclude w[i]
  SubsetSum(i+1, currSum, remaining - w[i])

Example

$S = \{3, 5, 6, 7\}$, target $T = 15$.

• Total remaining = 21.
• Include 3 (sum=3) → include 5 (8) → include 6 (14) → include 7 (21>15) ✗; exclude 7 (14≠15) ✗.
• Include 3 (3) → include 5 (8) → exclude 6 → include 7 (15) ✓ → subset {3, 5, 7} = 15.
• Continuing also finds {3, 6, ...} no; another solution is none further equal.

Solution subset: {3, 5, 7} (sum 15).

Complexity

Worst case $O(2^n)$ (binary choice per element); bounding functions prune large portions of the tree in practice.

Approximation Algorithms

Many optimization problems are NP-hard, so no known polynomial-time algorithm produces the exact optimum. An approximation algorithm runs in polynomial time and produces a solution provably close to optimal. Its quality is measured by the approximation ratio $\rho$: for a minimization problem, $\frac{C}{C^*} \le \rho$, where $C$ is the algorithm's cost and $C^*$ the optimal. An algorithm with ratio $\rho$ is called a $\rho$-approximation.

Approximation for Vertex Cover

Vertex Cover: find a minimum-size set of vertices $S$ such that every edge has at least one endpoint in $S$. This is NP-hard. A simple 2-approximation:

ApproxVertexCover(G):
  C = {}
  E' = E(G)
  while E' is not empty:
     pick any edge (u,v) from E'
     C = C + {u, v}                  // add BOTH endpoints
     remove from E' all edges incident to u or v
  return C

Why it is a 2-approximation: The edges picked in the loop form a matching (no two share a vertex). Any vertex cover must include at least one endpoint of each picked edge, so $|C^*| \ge$ (number of picked edges) $= |C|/2$. Hence $|C| \le 2|C^*|$, giving approximation ratio 2.

Runtime: $O(V + E)$. The algorithm is guaranteed never to exceed twice the optimal cover size.

Branch and Bound

Branch and Bound (B&B) is a technique for solving optimization problems (typically NP-hard) by systematically exploring a state-space tree. At each node it computes a bound — an optimistic estimate (lower bound for minimization) of the best solution obtainable in that subtree. If a node's bound is worse than the best complete solution found so far (the incumbent), the entire subtree is pruned (not explored).

Key elements:

• Branching: split the problem into subproblems (children nodes).
• Bounding: compute a lower/upper bound for each node.
• Pruning: discard nodes that cannot improve the incumbent.
• Search order may be BFS (FIFO), DFS (LIFO), or best-first (least-cost) using a priority queue.

Unlike backtracking (which only checks feasibility), B&B uses a cost bound to prune even feasible-but-suboptimal branches.

B&B for Travelling Salesman Problem (TSP)

TSP: find a minimum-cost tour visiting every city exactly once and returning to the start.

State-space tree: each level fixes the next city in the tour. For each node compute a lower bound on the cost of any complete tour through that partial path. A common bound:

adjusted as edges are committed along the partial path.

Procedure:

1. Start at city 1; compute root lower bound.
2. Branch to each unvisited city; for each child compute its lower bound from the reduced cost matrix.
3. Use a priority queue (best-first): expand the node with the smallest bound.
4. When a complete tour is reached, update the incumbent (best tour cost).
5. Prune any node whose bound ≥ incumbent.
6. Continue until the queue is empty; the incumbent is the optimal tour.

B&B avoids exploring the full $(n-1)!$ permutations by pruning, though the worst case remains exponential.

BFS vs DFS

Both are graph-traversal algorithms visiting every vertex/edge, but differ in order and data structure.

Example

Graph: A–B, A–C, B–D, C–D, D–E. Start at A.

• BFS order: A, B, C, D, E (visit A's neighbors first, then theirs).
• DFS order: A, B, D, C, E (or A, B, D, E, C depending on neighbor order) — dives deep before backtracking.

Time Complexity

For a graph with $V$ vertices and $E$ edges, using adjacency lists both run in:

Using an adjacency matrix, both are $O(V^2)$. Space complexity is $O(V)$ for the queue/stack and visited array.

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

(a) Substitution Method

Guess: $T(n) = O(n \log n)$. We prove $T(n) \le c\,n \log n$ for suitable $c$.

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

This is $\le c\,n\log n$ provided $-c\,n + n \le 0$, i.e. $c \ge 1$. The induction holds, so $T(n) = O(n\log n)$. A matching lower bound gives $T(n) = \Theta(n\log n)$.

(b) Recursion Tree Method

Expand the recurrence:

• Level 0: cost $n$ (1 node).
• Level 1: 2 nodes, each cost $n/2$ → total $n$.
• Level 2: 4 nodes, each cost $n/4$ → total $n$.
• Level $i$: $2^i$ nodes, each cost $n/2^i$ → total $n$.

Every level costs exactly $n$. The tree has height $\log_2 n$ (until subproblem size = 1), so the number of levels is $\log_2 n + 1$.

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

Answer: $T(n) = \Theta(n \log n)$.

Job Sequencing with Deadlines

Problem: Given $n$ jobs, each with a deadline $d_i$ and a profit $p_i$, where each job takes one unit of time and only one job runs at a time, schedule a subset of jobs (each before/at its deadline) to maximize total profit.

Greedy strategy: Sort jobs by profit in descending order. Consider each job and assign it to the latest free time slot $\le$ its deadline. If no slot is free, skip the job. Picking high-profit jobs first and scheduling them as late as possible keeps earlier slots open for other jobs.

JobSequencing(jobs):
  sort jobs by profit descending
  maxD = max deadline; slot[1..maxD] = free
  result = {}
  for each job j in sorted order:
     for t = min(maxD, j.deadline) downto 1:
        if slot[t] is free:
           slot[t] = j; add j to result; break
  return result

Example

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

• B(d1): slot1 free → place at slot1.
• A(d2): slot2 free → place at slot2.
• D(d1): slot1 taken → skip.
• C(d2): slots 1,2 taken → skip.
• E(d3): slot3 free → place at slot3.

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

Complexity

Sorting $O(n \log n)$; slot assignment $O(n \cdot maxD)$ → $O(n^2)$ in the naive version (improvable to $O(n \log n)$ with disjoint-set for free-slot lookup).