Analysis Design of Algorithm (CS-402) Unit 4 Notes

How unit 4 is examined

This unit covers backtracking (8-queens, Hamiltonian cycle, graph coloring), branch and bound (knapsack, TSP), lower bound theory and parallel algorithms; TSP, 8-queens, lower bounds and parallel algorithms carry the most marks.

Backtracking concept

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Backtracking is a systematic depth-first search of the state space tree in which a partial solution is abandoned (pruned) as soon as it cannot lead to a valid complete solution, and the search returns to the last choice point.</mark>

Key points.

The solution is a vector $(x_1, x_2, \dots, x_n)$ built one component at a time, so the search follows a state space tree.
Explicit constraints say which values each $x_i$ may take; implicit constraints say how the $x_i$ must relate to each other.
A bounding (promising) function kills a node as soon as its partial vector cannot be extended, so whole subtrees are never visited.
Advantages: pruning makes it far faster than brute force, it needs memory only for the current path, and it is simple to code recursively.
Disadvantages: the worst case is still exponential, a weak bounding function gives no saving, and it can only be used when partial solutions can be tested.
Typical problems are n-queens, Hamiltonian cycle, graph coloring, subset sum and the knight's tour.

Knight's tour (Jun 2025). Model the $n^2$ squares as vertices, and a legal knight move as an edge; the tour is a Hamiltonian path of $n^2-1$ moves.

Step 1: mark start (x,y) as move 0; board[x][y] = 0.
Step 2: Tour(x, y, k): if k = n*n-1 return true.
Step 3: for each of the 8 moves (dx,dy) in (±1,±2),(±2,±1): (u,v) = (x+dx, y+dy).
Step 4: if 0<=u,v<n and board[u][v] is unvisited: board[u][v] = k+1; if Tour(u,v,k+1) return true; else board[u][v] = unvisited (backtrack).
Step 5: return false.

Trying the neighbour with the fewest onward moves first (Warnsdorff's rule) makes the search almost linear in practice; without it the worst case is $O(8^{n^2})$.

Answer frame. Open with the definition; state the two constraint types; develop points 3-6 with 8-queens as the one problem (advantages and disadvantages last); close with "backtracking = DFS + pruning". For the knight's tour give the model, moves, the algorithm above and Warnsdorff.

Asked: [7 marks] (Jun 2020) What is Backtracking? Discuss any one problem solved by backtracking. Also give its advantages and disadvantages. Asked: [7 marks] (Jun 2025) Given an $n \times n$ chessboard, a knight is placed on an arbitrary square $(x, y)$. Determine $n^2-1$ knight moves that visit every square once, if such a sequence exists. Present an algorithm.

8 queen's problem

Definition. <mark>The 8-queens problem is to place 8 queens on an $8 \times 8$ chessboard so that no two queens share a row, a column or a diagonal.</mark>

Diagram. State space tree of 4-queens (X = dead end, solution 2-4-1-3). Node label = queens placed so far as column numbers. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 304 326" width="304" height="326" role="img" aria-label="4-queens tree: 1st queen in col 1 fails after 13 and 142; 2nd branch reaches the solution 2413; branches 3 and 4 mirror 2 and 1"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="152.5" y1="39" x2="56" y2="103"/><line class="e" x1="152.5" y1="39" x2="140" y2="103"/><line class="e" x1="152.5" y1="39" x2="199" y2="103"/><line class="e" x1="152.5" y1="39" x2="249" y2="103"/><line class="e" x1="56" y1="103" x2="31" y2="167"/><line class="e" x1="56" y1="103" x2="81" y2="167"/><line class="e" x1="31" y1="167" x2="31" y2="231"/><line class="e" x1="81" y1="167" x2="81" y2="231"/><line class="e" x1="81" y1="231" x2="81" y2="295"/><line class="e" x1="140" y1="103" x2="140" y2="167"/><line class="e" x1="140" y1="167" x2="140" y2="231"/><line class="e" x1="140" y1="231" x2="140" y2="295"/><circle class="n" cx="152.5" cy="39" r="17"/><text class="t" x="152.5" y="39" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="56" cy="103" r="17"/><text class="t" x="56" y="103" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="31" cy="167" r="17"/><text class="t" x="31" y="167" dy=".35em" text-anchor="middle">13</text><circle class="n" cx="31" cy="231" r="17"/><text class="t" x="31" y="231" dy=".35em" text-anchor="middle">X1</text><circle class="n" cx="81" cy="167" r="17"/><text class="t" x="81" y="167" dy=".35em" text-anchor="middle">14</text><circle class="n" cx="81" cy="231" r="17"/><text class="t" x="81" y="231" dy=".35em" text-anchor="middle">142</text><circle class="n" cx="81" cy="295" r="17"/><text class="t" x="81" y="295" dy=".35em" text-anchor="middle">X2</text><circle class="n" cx="140" cy="103" r="17"/><text class="t" x="140" y="103" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="140" cy="167" r="17"/><text class="t" x="140" y="167" dy=".35em" text-anchor="middle">24</text><circle class="n" cx="140" cy="231" r="17"/><text class="t" x="140" y="231" dy=".35em" text-anchor="middle">241</text><rect class="n" x="114" y="280" width="52" height="30" rx="8"/><text class="t" x="140" y="295" dy=".35em" text-anchor="middle">2413</text><circle class="n" cx="199" cy="103" r="17"/><text class="t" x="199" y="103" dy=".35em" text-anchor="middle">3</text><circle class="n" cx="249" cy="103" r="17"/><text class="t" x="249" y="103" dy=".35em" text-anchor="middle">4</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">4-queens tree: 1st queen in col 1 fails after 13 and 142; 2nd branch reaches the solution 2413; branches 3 and 4 mirror 2 and 1</figcaption></figure>

Key points.

Since each row holds exactly one queen, the solution is a vector $(x_1, \dots, x_8)$ where $x_i$ is the column of the queen in row $i$.
Two queens at $(i, x_i)$ and $(j, x_j)$ attack each other if $x_i = x_j$ (same column) or $|x_i - x_j| = |i - j|$ (same diagonal).
Brute force tries $8^8$ (or $8!$ = 40,320 permutations); backtracking prunes a row-by-row placement the moment a queen is attacked.
Queens are placed row by row; if no safe column exists in a row, the algorithm backtracks to the previous row and moves that queen to its next column.
The state space tree has $1+8+8\cdot7+\dots$ nodes at most; pruning visits only a small fraction of them.
There are 92 solutions for 8 queens (12 distinct up to rotation and reflection); one is $(1,5,8,6,3,7,2,4)$.
Time complexity is $O(n!)$ in the worst case; 4-queens has exactly 2 solutions, $(2,4,1,3)$ and $(3,1,4,2)$.

Algorithm.

Place(k, i):   // can queen k go in column i?
  for j = 1 to k-1:
    if x[j] == i or |x[j] - i| == |j - k|: return false
  return true
NQueens(k, n):
  for i = 1 to n:
    if Place(k, i): x[k] = i
      if k == n: print x[1..n]
      else NQueens(k+1, n)

Example (4-queens, Jun 2026). Place queen 1 in column 2; queen 2 cannot use columns 1-3 (attacked), so column 4; queen 3 goes to column 1; queen 4 goes to column 3, giving $(2,4,1,3)$. The second solution $(3,1,4,2)$ is its mirror image (reflection about the vertical axis, $x_i \to 5-x_i$), so the two solutions are symmetric.

Row	Sol 1 (2,4,1,3)	Sol 2 (3,1,4,2)
1	. Q . .	. . Q .
2	. . . Q	Q . . .
3	Q . . .	. . . Q
4	. . Q .	. Q . .

Answer frame. Open with the definition of backtracking and the 8-queens statement; draw the 4-queens tree or the 8x8 board with $(1,5,8,6,3,7,2,4)$; develop points 1-4, then the algorithm, then complexity; close with the number of solutions (92). For the two 4-queens solutions, show the tree and the mirror relationship.

Pitfall: Forgetting the diagonal test $|x_j - i| = |j - k|$ loses the main mark.

Asked: [7 marks] (May 2019, Jun 2022, Jun 2023) What is backtracking? Explain the 8 queen's problem and how it is solved using backtracking. Asked: [7 marks] (Jun 2020) Construct the state space tree for the four queen's problem using backtracking. Asked: [7 marks] (Jun 2024, Dec 2024) Write an algorithm for the 8-queens problem using backtracking. Asked: [7 marks] (Jun 2026) Obtain any 2 solutions to the 4-queen's problem. Establish the relationship between them.

Hamiltonian cycle

Definition. <mark>A Hamiltonian cycle is a closed path in a graph that visits every vertex exactly once and returns to the start vertex.</mark>

Key points.

The solution vector is $(x_1, \dots, x_n)$ with $x_1 = 1$; $x_k$ is the $k$-th vertex on the cycle.
NextValue(k) picks the next vertex for $x_k$ that is adjacent to $x_{k-1}$ and not already used; for $k = n$ it must also be adjacent to $x_1$.
If NextValue finds none, the algorithm backtracks to $x_{k-1}$; for the graph 1-2, 2-3, 3-4, 4-1, 1-3 the trace $1 \to 2 \to 3 \to 4 \to 1$ succeeds.
The worst-case time is $O(n!)$, about $O(n^n)$.

Asked: [7 marks] (Jun 2026) What is Hamiltonian cycle? Explain how it can be solved using backtracking.

Graph coloring problem

Definition. <mark>Graph coloring assigns colors to vertices so that no two adjacent vertices get the same color; the m-coloring problem asks whether this is possible with at most $m$ colors, and the smallest such $m$ is the chromatic number $\chi(G)$.</mark>

Diagram. State space tree for $n = 3$, $m = 3$ (only the first branch of each level is expanded; the others are identical). Label = colors of vertices so far. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 386 262" width="386" height="262" role="img" aria-label="m-coloring tree: each node has m = 3 children; levels 0-3 hold 1, 3, 9, 27 nodes"><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="243.5" y1="39" x2="156" y2="103"/><line class="e" x1="243.5" y1="39" x2="281" y2="103"/><line class="e" x1="243.5" y1="39" x2="331" y2="103"/><line class="e" x1="156" y1="103" x2="81" y2="167"/><line class="e" x1="156" y1="103" x2="181" y2="167"/><line class="e" x1="156" y1="103" x2="231" y2="167"/><line class="e" x1="81" y1="167" x2="31" y2="231"/><line class="e" x1="81" y1="167" x2="81" y2="231"/><line class="e" x1="81" y1="167" x2="131" y2="231"/><circle class="n" cx="243.5" cy="39" r="17"/><text class="t" x="243.5" y="39" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="156" cy="103" r="17"/><text class="t" x="156" y="103" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="81" cy="167" r="17"/><text class="t" x="81" y="167" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="31" cy="231" r="17"/><text class="t" x="31" y="231" dy=".35em" text-anchor="middle">111</text><circle class="n" cx="81" cy="231" r="17"/><text class="t" x="81" y="231" dy=".35em" text-anchor="middle">112</text><circle class="n" cx="131" cy="231" r="17"/><text class="t" x="131" y="231" dy=".35em" text-anchor="middle">113</text><circle class="n" cx="181" cy="167" r="17"/><text class="t" x="181" y="167" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="231" cy="167" r="17"/><text class="t" x="231" y="167" dy=".35em" text-anchor="middle">13</text><circle class="n" cx="281" cy="103" r="17"/><text class="t" x="281" y="103" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="331" cy="103" r="17"/><text class="t" x="331" y="103" dy=".35em" text-anchor="middle">3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">m-coloring tree: each node has m = 3 children; levels 0-3 hold 1, 3, 9, 27 nodes</figcaption></figure>

Key points.

The solution vector is $(x_1, \dots, x_n)$ where $x_i \in \{1, \dots, m\}$ is the color of vertex $i$.
Vertex $k$ may take color $c$ only if no already-colored neighbour has color $c$; otherwise the next color is tried, and if all $m$ fail the search backtracks.
The tree has $m^n$ leaves and $\sum_{i=0}^{n} m^i = (m^{n+1}-1)/(m-1)$ nodes, which is $1+3+9+27 = 40$ for $n=m=3$.
Worst-case time is $O(n\,m^n)$.
Applications include map coloring, timetable and exam scheduling, and register allocation.

Example (Nov 2019). Edges A1-A2, A1-A3, A1-A4, A3-A4, A2-A4. Color A1 = 1; A2 (adjacent to A1) = 2; A3 (adjacent to A1) = 2; A4 (adjacent to A1, A2, A3) = 3. Minimum colors = 3, because A1-A3-A4 is a triangle. For the 6-vertex graph (Dec 2024), a-b-c is a triangle, so start a=1, b=2, c=3 and continue the same way; $\chi = 3$.

Answer frame. Open with the definition and $\chi(G)$; draw the tree with 3 branches per level; then the backtracking rule and node count; close with the colored graph and its minimum number of colors.

Asked: [7 marks] (Jun 2024, Dec 2024) Draw the state space tree for m coloring when $n = 3$ and $m = 3$; explain graph coloring for the given graph. Asked: [7 marks] (Nov 2019) Colour the given graph using a vertex colouring algorithm. What is the minimum number of colours required?

Introduction to branch and bound

Definition. <mark>Branch and bound is a state space search for optimization problems that generates the children of a live node (branching) and discards any node whose bound shows it cannot beat the best solution found so far (bounding).</mark>

Key points.

Every node has a bound; for maximisation an upper bound (for minimisation a lower bound) is computed, and nodes worse than the best known answer are killed.
FIFO branch and bound keeps live nodes in a queue, so the tree is explored breadth-first, level by level.
LIFO branch and bound uses a stack, giving depth-first order.
LC (least-cost) branch and bound picks the live node with the best bound from a priority queue; it usually finds the answer sooner.
Unlike backtracking, which is DFS for any solution, branch and bound is used for optimization and can be BFS or best-first.
Worst-case time is exponential, $O(2^n)$ for knapsack.

Example: 0/1 knapsack by LCBB (Nov 2023). $n=4$, $P=(10,10,12,18)$, $W=(2,4,6,9)$, $M=15$. Densities $P/W$ = 5, 2.5, 2, 2, so the items are already in order. The upper bound fills the bag greedily and takes a fraction of the first item that does not fit: at the root, items 1, 2, 3 give weight 12 and profit 32, plus $3/9$ of item 4 = 6, so $ub = 38$. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 1416 322" width="1416" height="322" role="img" aria-label="LCBB knapsack tree; x2=0 (36) and x1=0 (32) are pruned once 38 is reached"><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="1192" y1="37" x2="944" y2="101"/><line class="e" x1="1192" y1="37" x2="1316" y2="101"/><line class="e" x1="944" y1="101" x2="448" y2="165"/><line class="e" x1="944" y1="101" x2="1068" y2="165"/><line class="e" x1="448" y1="165" x2="200" y2="229"/><line class="e" x1="448" y1="165" x2="696" y2="229"/><line class="e" x1="200" y1="229" x2="76" y2="293"/><line class="e" x1="200" y1="229" x2="324" y2="293"/><line class="e" x1="696" y1="229" x2="572" y2="293"/><line class="e" x1="696" y1="229" x2="820" y2="293"/><rect class="n" x="1146.5" y="22" width="91" height="30" rx="8"/><text class="t" x="1192" y="37" dy=".35em" text-anchor="middle">Root ub38</text><rect class="n" x="898.5" y="86" width="91" height="30" rx="8"/><text class="t" x="944" y="101" dy=".35em" text-anchor="middle">x1=1 ub38</text><rect class="n" x="402.5" y="150" width="91" height="30" rx="8"/><text class="t" x="448" y="165" dy=".35em" text-anchor="middle">x2=1 ub38</text><rect class="n" x="154.5" y="214" width="91" height="30" rx="8"/><text class="t" x="200" y="229" dy=".35em" text-anchor="middle">x3=1 ub38</text><rect class="n" x="23" y="278" width="106" height="30" rx="8"/><text class="t" x="76" y="293" dy=".35em" text-anchor="middle">x4=1 w21 no</text><rect class="n" x="282.5" y="278" width="83" height="30" rx="8"/><text class="t" x="324" y="293" dy=".35em" text-anchor="middle">x4=0 p32</text><rect class="n" x="650.5" y="214" width="91" height="30" rx="8"/><text class="t" x="696" y="229" dy=".35em" text-anchor="middle">x3=0 ub38</text><rect class="n" x="515" y="278" width="114" height="30" rx="8"/><text class="t" x="572" y="293" dy=".35em" text-anchor="middle">x4=1 p38 OPT</text><rect class="n" x="778.5" y="278" width="83" height="30" rx="8"/><text class="t" x="820" y="293" dy=".35em" text-anchor="middle">x4=0 p20</text><rect class="n" x="1022.5" y="150" width="91" height="30" rx="8"/><text class="t" x="1068" y="165" dy=".35em" text-anchor="middle">x2=0 ub36</text><rect class="n" x="1270.5" y="86" width="91" height="30" rx="8"/><text class="t" x="1316" y="101" dy=".35em" text-anchor="middle">x1=0 ub32</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">LCBB knapsack tree; x2=0 (36) and x1=0 (32) are pruned once 38 is reached</figcaption></figure> Optimal: items 1, 2, 4, weight 15, profit 38.

Answer frame. Open with the definition and the three strategies (FIFO, LIFO, LC); for knapsack draw the tree with bound, weight and profit on each node and cross out pruned nodes; close with the optimum (38). For FIFO, explain the queue, then bounding, then pruning.

Asked: [7 marks] (Nov 2023) Draw the portion of state space tree generated by LCBB for the knapsack instance $n=4$, $P=(10,10,12,18)$, $W=(2,4,6,9)$, $M=15$. Asked: [7 marks] (Dec 2024) Explain in detail about the FIFO branch and bound. Asked: [7 marks] (Jun 2024) Using branch and bound technique explain the 0/1 knapsack problem.

Traveling salesman problem

Definition. <mark>The traveling salesman problem asks for the minimum-cost tour that starts at a city, visits every other city exactly once and returns to the start; it is a minimum-cost Hamiltonian cycle.</mark>

Key points.

The input is an $n \times n$ cost matrix with $\infty$ on the diagonal, and a tour is a permutation of cities whose cost is the sum of its $n$ edges.
Reduction: subtract each row's minimum from that row, then each column's minimum from that column; the sum of subtracted values is the lower bound of the root.
To branch on edge $(i,j)$: set row $i$ and column $j$ to $\infty$, set $M[j][i] = \infty$ to forbid a premature return, reduce again, and set $\hat c(child) = \hat c(parent) + M[i][j] + r$, where $r$ is the new reduction.
LC search always expands the live node with the least $\hat c$; a node with $\hat c \ge$ best known tour is pruned; the first complete tour popped is optimal.
Complexity: brute force is $O((n-1)!)$ and branch and bound is $O(n!)$ in the worst case, while Held-Karp dynamic programming takes $O(n^2 2^n)$.
TSP is NP-hard; practical approximation (MST-based, twice the optimum) works for metric costs.

LC-Search control abstraction (Jun 2023).

Step 1: E = root; H = empty priority queue (min c-hat).
Step 2: loop: for each child X of E: if X is an answer node, print path and return; Add(X) to H with c-hat(X).
Step 3: if H is empty: print "no answer"; return.
Step 4: E = Delete-least(H); go to Step 2.

Example 1 (3x3, Nov 2019 / Jun 2022 / Jun 2025). Row minima 3, 4, 3 (sum 10); columns are then already reduced, so the root bound is 10 with reduced matrix rows $(\infty,0,1),(2,\infty,0),(0,2,\infty)$.

Node	Working	Bound
A to B	reduced matrix stays reduced, $r=0$	$10+0+0 = 10$
A to C	$10+1+r$, $r=2+2=4$	15
A-B-C	forced return C to A costs 0	10

Optimal tour A-B-C-A, cost $3+4+3 = 10$.

Example 2 (5x5, Jun 2025). Row minima 3, 3, 5, 3, 8 sum to 22 and the columns then subtract 5, so the root bound is 27. Children of A: B 34, C 29, D 38, E 28. LC expands E (28): A-E-B 36, A-E-C 29, A-E-D 29. Next A-C (29) gives 33, 35, 35, all worse than 29; A-E-C (29) leads to A-E-C-D (29), then A-E-C-D-B (29). Optimal tour A-E-C-D-B-A, cost $8+9+6+3+3 = 29$.

Generalised Hamiltonian (Nov 2023). Keep the backtracking Hamiltonian procedure, add the running cost $c$ and global best $B = \infty$.

Step 1: x[1] = 1; c = 0. Extend(k, c):
Step 2: for each vertex v not in x, adjacent to x[k-1]: c' = c + cost[x[k-1]][v].
Step 3: if c' >= B, skip v (all costs are positive, so the cost only grows).
Step 4: if k = n and edge v to x[1] exists: total = c' + cost[v][x[1]]; if total < B then B = total, save x.
Step 5: else x[k] = v; Extend(k+1, c'); unmark v.

Time $O(n!)$, pruned in practice.

Answer frame. For the numerical, write the matrix, reduction and root bound, one bound per child in a tree, mark the least-cost path and the final tour cost in bold. For "explain", open with the definition, then the bounding function, reduction, branching, LC rule, example and complexity $O(n!)$ (worse than $O(n^2 2^n)$ DP). For LC-Search, write the abstraction first, then the TSP steps.

Pitfall: Forgetting to set $M[j][i] = \infty$ (return edge) and to add $M[i][j]$ to the child bound gives wrong bounds.

Asked: [7 marks] (Nov 2019, Jun 2022, Jun 2025) Solve the TSP using Branch and Bound for the 3x3 matrix A: $\infty,3,4$; B: $6,\infty,4$; C: $3,5,\infty$. Asked: [7 marks] (Jun 2020) Explain how to solve the TSP by branch and bound and analyze the complexity. Asked: [7 marks] (Nov 2023) Generalize Hamiltonian so that it finds a minimum-cost Hamiltonian cycle in a graph with positive edge costs. Asked: [14 marks] (Jun 2023) Write the control abstraction for LC-Search. Explain how the TSP is solved using LCBB. Asked: [7 marks] (Jun 2025) Solve the TSP instance with the 5x5 cost matrix $(\infty,7,3,12,8;\ 3,\infty,6,14,9;\ 5,8,\infty,6,18;\ 9,3,5,\infty,11;\ 18,14,9,8,\infty)$. Asked: [7 marks] (Jun 2026) Explain Travelling Salesman Problem in detail.

Lower bound theory and its use in algebraic problems

Definition. <mark>Lower bound theory gives a function $L(n)$ such that every algorithm for the problem must take at least $L(n)$ time or operations, written $\Omega(L(n))$; an algorithm with this running time is therefore optimal.</mark>

Diagram. Comparison tree for sorting 3 elements (6 leaves). <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 536 262" width="536" height="262" role="img" aria-label="Decision tree for n = 3: 3! = 6 leaves, height 3"><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="256" y1="39" x2="80" y2="103"/><line class="e" x1="256" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="168" y1="167" x2="212" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="432" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><circle class="n" cx="256" cy="39" r="17"/><text class="t" x="256" y="39" dy=".35em" text-anchor="middle">a:b</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">b:c</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">abc</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">a:c</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">acb</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">cab</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">a:c</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">bac</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">b:c</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">bca</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">cba</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Decision tree for n = 3: 3! = 6 leaves, height 3</figcaption></figure>

Key points.

A lower bound is proved for all algorithms of a model, not just one algorithm, so it tells us when to stop searching for a faster one.
Trivial bounds count the input and output: computing all $n^2$ entries of a matrix product needs $\Omega(n^2)$.
Comparison trees model comparison-based algorithms: each internal node is a comparison, each leaf is an outcome, and running time is the length of a root-to-leaf path.
Adversary (oracle) arguments answer each comparison so as to force the most work; finding the maximum of $n$ items needs $n-1$ comparisons, and max plus min together need $\lceil 3n/2 \rceil - 2$.
Searching a sorted list by comparisons needs $\lceil \log_2(n+1) \rceil$, so binary search is optimal.
Polynomial evaluation: Horner's rule uses $n$ multiplications and $n$ additions, which is optimal.

Sorting proof (Nov 2023).

The comparison tree is binary, and it must have at least $n!$ leaves, one per permutation of the input.
A binary tree of height $h$ has at most $2^h$ leaves, so $2^h \ge n!$ and $h \ge \log_2 n!$.
$n! \ge (n/2)^{n/2}$, hence $\log_2 n! \ge \frac{n}{2}\log_2\frac{n}{2} = \Omega(n\log n)$.

Every comparison sort needs $\Omega(n \log n)$ comparisons in the worst case, so merge sort and heap sort are optimal.

Answer frame. Open with the definition and $\Omega$; give the 3-element comparison tree; develop points 1-6 (techniques first, then sorting, searching, max, polynomial); close with the $\Omega(n\log n)$ result. For the proof question, write the three proof steps in order.

Asked: [7 marks] (May 2019, Dec 2020, Jun 2026) What is the meaning of Lower bound theory and how can it be used in solving algebraic problems? Asked: [7 marks] (Nov 2023) How can comparison trees be used for deriving lower bounds on the problem of sorting?

Introduction to parallel algorithms

Definition. <mark>A parallel algorithm solves a problem by dividing it into parts that are executed at the same time on several processors, to finish faster than a sequential algorithm.</mark>

Key points.

The need: single-processor speed has hit physical limits, and large problems (weather, graphics, search) must be finished in reasonable time.
PRAM is the standard model: $p$ processors share a common memory and run in lockstep; variants are EREW (exclusive read and write), CREW and CRCW (concurrent write).
Machine classes are SIMD (one instruction on many data items) and MIMD (different instructions on different data).
Speedup is $S = T_1 / T_p$, efficiency is $E = S / p$, and cost (work) is $p \cdot T_p$; an algorithm is cost-optimal if the cost equals $T_1$.
Example: adding $n$ numbers by pairing takes $\log_2 n$ steps on $n/2$ processors; for $n=8$, $T_1=7$, $T_p=3$, $S = 2.33$, $E = 2.33/4 = 0.58$.
Other examples are parallel merge sort, parallel quick sort, matrix multiplication and parallel prefix sums; applications are simulation, image processing, databases and machine learning.

Graph coloring (short note). Color vertices so that adjacent ones differ; the minimum number of colors is the chromatic number, found by backtracking or greedy coloring (a triangle needs 3), with uses in scheduling and register allocation. Quick sort (short note). Partition around a pivot, then sort both parts recursively; average $O(n \log n)$, worst case $O(n^2)$.

Answer frame. Open with the definition and need; draw a small PRAM (processors P1..Pp joined to a shared memory); develop points 2-6; close with speedup and efficiency. For a two-part short note give each part a definition, a point or two and one example.

Asked: [7 marks] (Jun 2020, Jun 2022) Give a brief note on (i) Parallel algorithms (ii) Graph coloring (iii) Quick sort. Asked: [7 marks] (May 2019) Write a detailed note on Parallel Algorithms.

Last-minute revision

Backtracking = DFS on the state space tree + a bounding function that prunes dead branches.
n-queens attack test: same column $x_i = x_j$ or same diagonal $|x_i - x_j| = |i-j|$.
8-queens has 92 solutions (12 distinct); 4-queens has 2: $(2,4,1,3)$ and $(3,1,4,2)$.
Hamiltonian cycle: $x_1 = 1$, each next vertex adjacent and unused, the last adjacent to $x_1$; time $O(n!)$.
m-coloring tree has $(m^{n+1}-1)/(m-1)$ nodes; time $O(n\,m^n)$; $\chi$ = the least $m$ that works.
FIFO B&B uses a queue, LIFO a stack, LC a priority queue on the best bound.
Knapsack LCBB ($M=15$): items 1, 2, 4, weight 15, profit 38.
TSP bound: reduce rows then columns; child bound = parent + $M[i][j]$ + new reduction.
TSP 3x3 answer A-B-C-A = 10; 5x5 answer A-E-C-D-B-A = 29 (root bound 27).
Comparison-sort lower bound: $2^h \ge n!$ so $h = \Omega(n \log n)$.
Speedup $T_1/T_p$, efficiency $S/p$.

Memory hooks

Backtracking: "go deep, hit a wall, step back".
Queens: "row, column, diagonal" - one per row, so only the last two need checking.
FIFO = Queue (line at a counter); LIFO = Stack (plates); LC = Priority queue (VIP).
TSP bound: "Reduce, Reserve, Recurse": rows and columns, forbid the return edge, expand the cheapest.
Lower bound: leaves at least $n!$, height at least $\log n!$.

Coverage checklist

Backtracking concept: Jun 2020 (definition, advantages, one problem), Jun 2025 (knight's tour).
8 queen's problem: May 2019 / Jun 2022 / Jun 2023 (explain), Jun 2020 (4-queens tree), Jun 2024 / Dec 2024 (algorithm), Jun 2026 (two 4-queens solutions).
Hamiltonian cycle: Jun 2026 (definition and backtracking).
Graph coloring problem: Jun 2024 / Dec 2024 (state space tree m=3, n=3), Nov 2019 (colour the graph, minimum colours).
Introduction to branch & bound method: Nov 2023 (LCBB knapsack tree), Dec 2024 (FIFO), Jun 2024 (0/1 knapsack).
traveling salesman problem: Nov 2019 / Jun 2022 / Jun 2025 (3x3), Jun 2020 (explain and complexity), Nov 2023 (generalised Hamiltonian), Jun 2023 (LC-Search and LCBB), Jun 2025 (5x5), Jun 2026 (explain).
Meaning of lower bound theory and its use in solving algebraic problem: May 2019 / Dec 2020 / Jun 2026 (meaning and use), Nov 2023 (comparison tree for sorting).
introduction to parallel algorithms: Jun 2020 / Jun 2022 (note with graph coloring), May 2019 (detailed note).

Account

Analysis Design of Algorithm (CS-402) - Unit 4 Short Notes

How unit 4 is examined

Backtracking concept

8 queen's problem

Hamiltonian cycle

Graph coloring problem

Introduction to branch and bound

Traveling salesman problem

Lower bound theory and its use in algebraic problems

Introduction to parallel algorithms

Last-minute revision

Memory hooks

Coverage checklist