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

Dynamic Programming

Dynamic Programming (DP) is an algorithm-design technique for solving problems that exhibit:

1. Optimal substructure — an optimal solution is built from optimal solutions of subproblems.
2. Overlapping subproblems — the same subproblems recur many times.

DP solves each subproblem once, stores its result in a table (memoization / tabulation), and reuses it, avoiding the exponential blow-up of plain recursion.

Floyd-Warshall Algorithm (All-Pairs Shortest Paths)

Given a weighted graph with $n$ vertices, Floyd-Warshall finds the shortest distance between every pair of vertices. It allows negative edges (but no negative cycles).

Idea: Let $d_{ij}^{(k)}$ = shortest distance from $i$ to $j$ using only intermediate vertices from $\{1,2,\dots,k\}$. The recurrence is:

with base case $d_{ij}^{(0)} = w(i,j)$ (edge weight, $\infty$ if no edge, $0$ if $i=j$).

FLOYD-WARSHALL(W, n):
    D = W                       // copy weight matrix
    for k = 1 to n:
        for i = 1 to n:
            for j = 1 to n:
                if D[i][k] + D[k][j] < D[i][j]:
                    D[i][j] = D[i][k] + D[k][j]
    return D

Example

Consider 3 vertices with weight matrix (row = from, col = to, $\infty$ = no edge):

• k = 1: no improvement through vertex 1 yet.
• k = 2: $d_{13} = \min(\infty, d_{12}+d_{23}) = \min(\infty, 8+1) = 9$.
• k = 3: $d_{21} = \min(\infty, d_{23}+d_{31}) = \min(\infty, 1+4) = 5$; $d_{11}$ stays 0.

Final all-pairs shortest distances:

Time and Space Complexity

Three nested loops over $n$ vertices give time complexity $O(n^3)$ and space complexity $O(n^2)$ for the distance matrix.

Greedy Method

The greedy method builds a solution piece by piece, at every step choosing the option that looks best right now (the locally optimal / greedy choice), never reconsidering it. It yields a globally optimal solution when the problem has the greedy-choice property and optimal substructure (e.g. Huffman coding, fractional knapsack, Dijkstra, MST). It is simple and fast but does not work for every optimization problem.

Huffman Coding of "CYBER CRIME"

Step 1 — Frequencies (string length = 11, 8 distinct symbols):

Step 2 — Build the Huffman tree. Repeatedly remove the two lowest-frequency nodes, merge them into a node whose weight is their sum, and reinsert it, until one node (root, weight 11) remains. Merging the five weight-1 symbols and three weight-2 symbols produces a nearly balanced tree of depth 3.

Step 3 — Assign codes (left = 0, right = 1). One valid prefix-free code set:

(Exact bit-strings may differ between valid Huffman trees, but the optimal lengths and total are the same.)

Step 4 — Total bits required:

Each symbol turns out to use 3 bits because the frequencies are nearly uniform, so Huffman gives the same 33 bits as a fixed 3-bit code here. The codes are prefix-free (no code is a prefix of another), allowing unambiguous decoding.

Backtracking

Backtracking is a systematic, depth-first search of the solution space that builds candidates incrementally and abandons a partial candidate ("backtracks") as soon as it determines the candidate cannot be extended to a valid complete solution (a bounding / feasibility check). It is used for constraint-satisfaction problems such as N-Queens, graph colouring, and subset-sum.

Backtracking vs. Recursion

In short, backtracking is recursion plus pruning and state-undoing.

4-Queens Problem

Place 4 queens on a 4×4 board so that no two share a row, column, or diagonal. We place one queen per row and try columns left-to-right, pruning placements that conflict with already-placed queens.

Search (showing one successful line):

• Row 1: place Q at col 1.
• Row 2: cols 1,2 conflict (col/diagonal); col 3 is safe → place at col 3.
• Row 3: cols 1,2,3,4 all conflict → backtrack to row 2.
• Row 2: try col 4 → safe.
• Row 3: col 2 is safe → place at col 2.
• Row 4: col 4 attacks diagonally; col... only col... none with start col1 → backtrack further.
• Eventually starting Row 1 at col 2 succeeds:

Solution 1: (row, col) = (1,2), (2,4), (3,1), (4,3)

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

Solution 2 (mirror): (1,3), (2,1), (3,4), (4,2)

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

The 4-Queens problem has exactly 2 solutions.

Time Complexity

Without pruning, placing one queen per row over $n$ columns gives $O(n^n)$; with the column-permutation structure it is $O(n!)$. For $n=4$ the worst case is bounded by $4! = 24$ leaf possibilities, drastically reduced by the diagonal/column pruning. In general N-Queens backtracking runs in $O(n!)$ worst-case time, far better than brute force $\binom{n^2}{n}$.

Fractional Knapsack — Greedy Algorithm

Problem: Given $n$ items with values $v_i$ and weights $w_i$, and a knapsack of capacity $W$, maximize total value where items may be taken fractionally (a fraction $x_i \in [0,1]$ of each).

Greedy idea: Take items in decreasing order of value-to-weight ratio $v_i/w_i$, filling the knapsack until it is full (taking a fraction of the last item if needed). This is optimal for the fractional version.

FRACTIONAL-KNAPSACK(v[], w[], n, W):
    for i = 1 to n:
        ratio[i] = v[i] / w[i]
    sort items by ratio in decreasing order
    totalValue = 0;  remaining = W
    for i = 1 to n:
        if w[i] <= remaining:
            take whole item i
            totalValue += v[i];  remaining -= w[i]
        else:
            take fraction (remaining / w[i]) of item i
            totalValue += v[i] * (remaining / w[i])
            break        // knapsack full
    return totalValue

Example: $W=20$; items $(v,w)$ = (60,10), (100,20), (120,30) with ratios 6, 5, 4. Take all of item 1 (value 60, used 10), then $10/20$ of item 2 (value 50) → total 110.

Time Complexity

• Computing ratios: $O(n)$.
• Sorting by ratio: $O(n \log n)$ (dominant).
• Single pass to fill: $O(n)$.

Overall time = $O(n \log n)$, space $O(1)$ extra.

Edit Distance: "ARTIFICIAL" → "NATURAL"

Edit (Levenshtein) distance = minimum number of insertions, deletions, and substitutions (each cost 1) to transform one string into another. With $A$="ARTIFICIAL" ($m=10$) and $B$="NATURAL" ($n=7$):

with $dp[i][0]=i$, $dp[0][j]=j$.

DP table (rows = ARTIFICIAL, cols = NATURAL):

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

The value at the bottom-right corner is the answer. (Time complexity $O(mn)$, space $O(mn)$.)

Dijkstra's Algorithm (Single-Source Shortest Paths)

Finds the shortest path from a source $s$ to every other vertex in a graph with non-negative edge weights. It is greedy: it repeatedly picks the unvisited vertex with the smallest tentative distance and relaxes its outgoing edges.

DIJKSTRA(G, w, s):
    for each vertex v: dist[v] = INFINITY
    dist[s] = 0
    Q = all vertices (min-priority queue keyed by dist)
    while Q not empty:
        u = EXTRACT-MIN(Q)          // closest unvisited vertex
        for each edge (u, v):
            if dist[u] + w(u,v) < dist[v]:   // relaxation
                dist[v] = dist[u] + w(u,v)
                parent[v] = u
    return dist, parent

Example

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

1. dist: A=0, others ∞. Pick A. Relax: B=4, C=1.
2. Pick C (1). Relax: B = min(4, 1+2)=3, D = 1+5 = 6.
3. Pick B (3). Relax: D = min(6, 3+1) = 4.
4. Pick D (4). Done.

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

Time Complexity

• Array implementation: $O(V^2)$.
• Binary-heap (priority queue): $O((V+E)\log V)$.

Dijkstra fails with negative edge weights (use Bellman-Ford instead).

Matrix Chain Multiplication

Problem: Given a chain of matrices $A_1, A_2, \dots, A_n$ where $A_i$ has dimension $p_{i-1} \times p_i$, find the order of multiplication (parenthesization) that minimizes the total number of scalar multiplications. Matrix multiplication is associative, so the result is the same, but the cost varies hugely with the order. Multiplying a $p \times q$ by a $q \times r$ matrix costs $p \cdot q \cdot r$ scalar multiplications.

Example of why order matters: $A_1(10\times100)\,A_2(100\times5)\,A_3(5\times50)$.

• $((A_1A_2)A_3)$: $10\cdot100\cdot5 + 10\cdot5\cdot50 = 5000+2500 = 7500$.
• $(A_1(A_2A_3))$: $100\cdot5\cdot50 + 10\cdot100\cdot50 = 25000+50000 = 75000$.

The first order is 10× cheaper.

Dynamic Programming Formulation

Let $m[i][j]$ = minimum cost to multiply $A_i \cdots A_j$. Then:

Here $k$ is the split point; $s[i][j]=k$ records the optimal split for reconstructing the parenthesization.

MATRIX-CHAIN-ORDER(p, 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] = INFINITY
            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]

Time complexity $O(n^3)$, space $O(n^2)$. The answer is $m[1][n]$.

Heap Sort

Heap sort sorts an array using a binary max-heap (a complete binary tree where every parent ≥ its children, stored in an array; for index $i$: left child $2i+1$, right child $2i+2$).

Steps:

1. Build a max-heap from the input array (BUILD-MAX-HEAP, $O(n)$).
2. Repeatedly extract the max: swap the root (largest) with the last element, shrink the heap by 1, and MAX-HEAPIFY the root to restore the heap property.

HEAP-SORT(A, n):
    BUILD-MAX-HEAP(A, n)
    for i = n downto 2:
        swap A[1] and A[i]      // largest goes to the end
        heapSize = i-1
        MAX-HEAPIFY(A, 1, heapSize)

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,4,5,10].
• Swap 3↔1 → [1,3,4,5,10].
• Sorted: [1, 3, 4, 5, 10].

Time Complexity

• BUILD-MAX-HEAP: $O(n)$.
• Each of $n$ extractions does a MAX-HEAPIFY costing $O(\log n)$.

Overall: $O(n \log n)$ in best, average, and worst cases. Space is $O(1)$ (in-place); heap sort is not stable.

Subset-Sum by Backtracking

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

Backtracking approach: Traverse a binary state-space tree — at each element decide include (left) or exclude (right). Maintain the running sum and prune a branch (bound) when:

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

SUBSET-SUM(w, n, T):
    sort w ascending
    backtrack(index=0, currentSum=0, chosen=[])

backtrack(i, sum, chosen):
    if sum == T: report chosen; return
    if i == n or sum > T: return            // prune
    if sum + remainingSum(i) < T: return    // prune
    backtrack(i+1, sum + w[i], chosen + [w[i]])   // include w[i]
    backtrack(i+1, sum, chosen)                   // exclude w[i]

Example

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

• Include 3 (sum 3) → include 5 (8) → include 6 (14) → exclude 7 (14 ≠ 15) → include 7 (21 > 15, prune). Backtrack.
• Include 3 (3) → include 5 (8) → exclude 6 → include 7 (15) → found {3, 5, 7}.
• Continuing finds {3, 6, ...} none; also no others.

Solution subset: {3, 5, 7} = 15.

Worst-case time is $O(2^n)$ (the full state-space tree), but pruning typically explores far fewer nodes.

Approximation Algorithms

Many important problems are NP-hard, so no known polynomial-time algorithm finds the exact optimum. An approximation algorithm runs in polynomial time and returns a solution provably close to optimal. For a minimization problem, an algorithm has approximation ratio $\rho$ if for every input:

where $C$ is the cost returned and $C^*$ is the optimal cost. A ratio-2 algorithm is also called a 2-approximation.

Vertex Cover — 2-Approximation

A vertex cover is a set of vertices covering every edge (each edge has at least one endpoint in the set); finding the minimum is NP-hard.

APPROX-VERTEX-COVER(G):
    C = empty set
    E' = all edges of G
    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 works: Each picked edge $(u,v)$ must have at least one endpoint in any optimal cover, so the optimum contains at least one of the picked edges' endpoints. The algorithm picks a matching $M$ (the chosen edges are vertex-disjoint), so $|C| = 2|M|$ while $C^* \ge |M|$. Hence:

This is a 2-approximation running in $O(V+E)$ time.

Example: Edges {(1,2),(2,3),(3,4)}. Pick (1,2) → C={1,2}, removes (1,2),(2,3). Pick (3,4) → C={1,2,3,4}. (Optimal here is {2,3}; the approximation gives ≤ twice the optimum size.)

Branch and Bound

Branch and Bound (B&B) is a technique for solving optimization problems exactly by systematically exploring a state-space tree, but pruning subtrees that cannot contain a better solution than one already found. Two operations:

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

Nodes are explored using FIFO, LIFO, or (most commonly) least-cost (best-first) order. B&B always finds the optimum, but is exponential in the worst case.

B&B for the Travelling Salesman Problem (TSP)

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

Applying B&B:

1. State-space tree: each node represents a partial tour (a sequence of cities visited so far).
2. Cost / lower bound at a node: a common bound = cost of the path already fixed plus a lower estimate for the rest, e.g. for each unvisited city add half the sum of its two minimum-cost incident edges (reduced-cost-matrix bound). This gives a guaranteed lower bound on any completion of the partial tour.
3. Branch: from a node, create a child for each unvisited next city.
4. Bound & prune: maintain the best complete tour found so far (upper bound). If a node's lower bound $\ge$ best tour cost, discard that node — its subtree cannot beat the incumbent.
5. Expand the most promising (lowest-bound) live node first until the live list is empty; the best complete tour found is optimal.

Result: B&B avoids enumerating all $(n-1)!$ tours by pruning, finding the exact optimal tour much faster on average (worst case still exponential).

BFS vs. DFS

Both traverse all vertices of a graph; they differ in order and data structure.

• BFS explores level by level (all neighbours of a vertex before going deeper) using a queue (FIFO).
• DFS explores as deep as possible along one branch before backtracking, using a stack (LIFO) or recursion.

Comparison Table

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, then D).
• DFS order: A, B, D, C (go deep A→B→D, backtrack, then C).

Time Complexity

Using an adjacency list, both visit every vertex and edge once:

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