Classic Algorithm Solutions: Step-by-Step Examples

1) DIJKSTRA (SSSP) — STEP TABLE (PAST-PAPER INSTANCE A)

Given edges: a→b(2), a→c(7), a→e(10), b→d(2), c→d(1), c→g(2), d→f(2), e→g(1), f→g(2). Source = a.
Rule: Pick unsettled vertex with minimum dist; relax outgoing edges.

Vertices:   a   b   c   d   e   f   g

Init:
Dist      = 0   2   7   ∞  10   ∞   ∞
S = ∅

Step 1: Pick a (min=0), S={a}
Relax from a: already set b=2, c=7, e=10
Dist      = 0   2   7   ∞  10   ∞   ∞

Step 2: Pick b (min=2), S={a,b}
Relax b→d: dist(d) = dist(b)+2 = 2+2 = 4
Dist      = 0   2   7   4  10   ∞   ∞

Step 3: Pick d (min=4), S={a,b,d}
Relax d→f: dist(f) = 4+2 = 6
Dist      = 0   2   7   4  10   6   ∞

Step 4: Pick f (min=6), S={a,b,d,f}
Relax f→g: dist(g) = 6+2 = 8
Dist      = 0   2   7   4  10   6   8

Step 5: Pick c (min=7), S={a,b,d,f,c}
Relax c→d: 7+1=8  (no, current d=4)
Relax c→g: 7+2=9  (no, current g=8)
Dist      = 0   2   7   4  10   6   8

Step 6: Pick g (min=8), S={a,b,d,f,c,g}
No outgoing improvement.

Step 7: Pick e (min=10), S={a,b,c,d,e,f,g}
Relax e→g: 10+1=11 (no, current g=8)

Final distances:
A=0, b=2, c=7, d=4, e=10, f=6, g=8

One shortest path to g:
A→b→d→f→g with cost 2+2+2+2 = 8

2) DIJKSTRA (SSSP) — STEP TRACE (PAST-PAPER INSTANCE B)

Edges (from diagram): a→b(10), a→c(5), a→e(7), b→c(2), c→b(3), b→d(1), c→d(9), c→e(2), e→d(6). Source = a

Vertices: a b c d e

Init:
Dist(a)=0, dist(b)=10, dist(c)=5, dist(e)=7, dist(d)=∞
S=∅

Step 1: Pick c (min=5), S={c}
Relax c→b: 5+3=8  <10  ⇒ dist(b)=8
Relax c→d: 5+9=14 <∞   ⇒ dist(d)=14
Relax c→e: 5+2=7  =7   ⇒ dist(e)=7 (no change)

Now: dist(a)=0, b=8, c=5, d=14, e=7

Step 2: Pick e (min=7), S={c,e}
Relax e→d: 7+6=13 <14 ⇒ dist(d)=13

Now: dist(a)=0, b=8, c=5, d=13, e=7

Step 3: Pick b (min=8), S={c,e,b}
Relax b→d: 8+1=9 <13  ⇒ dist(d)=9
Relax b→c: 8+2=10 >5  ⇒ no change

Now: dist(a)=0, b=8, c=5, d=9, e=7

Step 4: Pick d (min=9), done.

Final:
Dist(a)=0, dist(c)=5, dist(e)=7, dist(b)=8, dist(d)=9
Shortest path to d: a→c→b→d (5+3+1=9)

3) FLOYD–WARSHALL (APSP) — FULL “k” STEPS (PAST-PAPER)

Edges: 1→2(4), 1→3(−2), 2→3(3), 4→2(−1), 4→3(2).
Rule: Dk[i][j] = min(Dk−1[i][j], Dk−1[i][k] + Dk−1[k][j])

D0 (initial W; ∞ means no edge):
      1   2   3   4
1     0   4  -2   ∞
2     ∞   0   3   ∞
3     ∞   ∞   0   ∞
4     ∞  -1   2   0

K=1 (allow intermediate {1}):
Need i→1 and 1→j to improve. But for i≠1, D0[i][1]=∞.
So no entry improves.  D1 = D0.

K=2 (allow intermediates {1,2}):
Main candidate improvement is via node 2.
Check 4→3 via 2:
D1[4][2] + D1[2][3] = (-1) + 3 = 2
Current D1[4][3] = 2, so no improvement.
All other candidates involve ∞.  D2 = D1.

K=3 (allow intermediates {1,2,3}):
Node 3 has no outgoing edges (row 3 is ∞ except diagonal).
So i→3→j cannot improve anything.  D3 = D2.

K=4 (allow intermediates {1,2,3,4}):
Need i→4 and 4→j. But for i≠4, D3[i][4]=∞.
So no improvement.  D4 = D3 (final).

Final shortest-path matrix:
      1   2   3   4
1     0   4  -2   ∞
2     ∞   0   3   ∞
3     ∞   ∞   0   ∞
4     ∞  -1   2   0

Time = O(V^3), Space = O(V^2)

4) 0/1 KNAPSACK — “HOW TABLE IS FILLED” + BACKTRACK (PAST-PAPER)

Given: M=12, profits (1,6,18,22,28,43), weights (1,2,5,6,7,10).
State: DP[i][w] = max profit using first i items within capacity w.
Rule:
If Wi > w ⇒ DP[i][w]=DP[i−1][w]
Else DP[i][w]=max(DP[i−1][w], Pi + DP[i−1][w−Wi])

Step-scoring: show key cells (capacity 12) clearly

At w=12:

I=3 (W3=5,P3=18):
Exclude = DP2[12] = 7
Include = 18 + DP2[12-5]=18+DP2[7]=18+7=25
DP3[12] = max(7,25)=25

I=4 (W4=6,P4=22):
Exclude = DP3[12] = 25
Include = 22 + DP3[12-6]=22+DP3[6]=22+19=41
DP4[12] = 41

I=5 (W5=7,P5=28):
Exclude = DP4[12] = 41
Include = 28 + DP4[12-7]=28+DP4[5]=28+18=46
DP5[12] = 46

I=6 (W6=10,P6=43):
Exclude = DP5[12] = 46
Include = 43 + DP5[12-10]=43+DP5[2]=43+6=49
DP6[12] = 49  (OPTIMUM)

Backtracking steps (this is what examiners like)

Start at DP6[12]=49.
Compare with DP5[12]=46 → different ⇒ item-6 is selected.
Remaining capacity w = 12-10 = 2.

Now at i=5, w=2:
DP5[2]=6 equals DP4[2]=6 ⇒ item-5 not selected.
I=4, w=2: DP4[2]=6 equals DP3[2]=6 ⇒ item-4 not selected.
I=3, w=2: DP3[2]=6 equals DP2[2]=6 ⇒ item-3 not selected.
I=2, w=2: DP2[2]=6 differs from DP1[2]=1 ⇒ item-2 selected.
Remaining w = 2-2=0. Stop.

Selected items: {2,6}
Total weight = 2+10=12
Total profit = 6+43 = 49

5) i-th SMALLEST (QUICKSELECT) — FULL PARTITION SWAPS (PAST-PAPER)

A=(10,2,5,15,50,6,20,25), find 3rd smallest. Pivot = last element.

Partition-1 (pivot=25), Lomuto:
I=-1, j=0..6

J=0: 10≤25 → i=0, swap A0↔A0
A: (10,2,5,15,50,6,20,25)

J=1: 2≤25  → i=1, swap A1↔A1
A: (10,2,5,15,50,6,20,25)

J=2: 5≤25  → i=2, swap A2↔A2
A: (10,2,5,15,50,6,20,25)

J=3: 15≤25 → i=3, swap A3↔A3
A: (10,2,5,15,50,6,20,25)

J=4: 50>25 → do nothing

J=5: 6≤25  → i=4, swap A4↔A5
A: (10,2,5,15,6,50,20,25)

J=6: 20≤25 → i=5, swap A5↔A6
A: (10,2,5,15,6,20,50,25)

End: swap A[i+1]=A6 with pivot A7
A: (10,2,5,15,6,20,25,50)

Pivot is 7th element → 3rd smallest lies in left part:
(10,2,5,15,6,20)

Partition-2 (pivot=20) → pivot becomes 6th in that subarray → go left:
(10,2,5,15,6)

Partition-3 (pivot=6) → after partition:
(2,5,6,15,10)
Pivot is 3rd ⇒ 3rd smallest = 6