ASSIGNMENT – DESIGN & ANALYSIS OF

ALGORITHMS
Modules Covered: III, IV, V
Case Study: Smart National Logistics & Security Network (SNLSN)

QUESTION 1: Greedy Optimization

(a) Minimum Spanning Tree – Prim's & Kruskal's Algorithm

The SNLSN graph from the case study has cities/nodes: A, B, C, D, E, F, G, H

Edge list (extracted from the given graph diagram):

Edge Weight (Travel Time)

C–A 20
C–B 15
A–B 10
C–D 5
D–F 10
D–E 15
E–B 10
E–F 25
F–H 30
F–G 5
H–G 10
E–G 15
Prim's Algorithm – Step by Step
Algorithm: Start from any vertex, greedily add minimum weight edge connecting MST to non-MST
vertex.
Starting Vertex: C

Step MST Set Edge Weigh Reason

Added t
1 {C} C–D 5 Minimum edge from C
2 {C,D} C–B 15 Min edge from {C,D}
to unvisited
3 {C,D,B} A–B 10 Min edge from {C,D,B}
to unvisited
4 {C,D,B,A} B–E 10 Min edge from
{C,D,B,A} to unvisited
5 {C,D,B,A,E} D–F 10 Min edge from set to
unvisited; F–E=25>10
6 {C,D,B,A,E,F} F–G 5 Min edge from set to
unvisited
7 {C,D,B,A,E,F,G} H–G 10 Min edge connecting
H

MST Edges (Prim's): C–D(5), C–B(15), A–B(10), B–E(10), D–F(10), F–G(5), G–H(10)
Total MST Cost = 5+15+10+10+10+5+10 = 65 units

Kruskal's Algorithm – Step by Step

Algorithm: Sort all edges by weight. Add edge to MST if it doesn't form a cycle (using Union-Find).

Step 1: Sort all edges by weight:

Rank Edge Weight
1 C–D 5
2 F–G 5
3 A–B 10
4 B–E 10
5 D–F 10
6 G–H 10
7 C–B 15
8 D–E 15
9 E–G 15
10 F–H 30
11 E–F 25
 Rank Edge Weight
12 C–A 20

Step 2: Process edges using Union-Find (Disjoint Set):

Step Edge Wt Action Components
1 C–D 5 ADD (no cycle) {C,D}, {A},{B},{E},{F},{G},{H}
2 F–G 5 ADD (no cycle) {C,D},{F,G},{A},{B},{E},{H}
3 A–B 10 ADD (no cycle) {C,D},{F,G},{A,B},{E},{H}
4 B–E 10 ADD (no cycle) {C,D},{F,G},{A,B,E},{H}
5 D–F 10 ADD (no cycle) {C,D,F,G},{A,B,E},{H}
6 G–H 10 ADD (no cycle) {C,D,F,G,H},{A,B,E}
7 C–B 15 ADD – joins two {C,D,F,G,H,A,B,E} – MST
components Complete!
8 D–E 15 SKIP – forms cycle –

MST Edges (Kruskal's): C–D(5), F–G(5), A–B(10), B–E(10), D–F(10), G–H(10), C–B(15)
Total MST Cost = 5+5+10+10+10+10+15 = 65 units

(b) Comparison: Prim's vs Kruskal's Algorithm

Parameter Prim's Algorithm Kruskal's Algorithm

Approach Vertex-based greedy. Grows Edge-based greedy. Sorts
MST one vertex at a time. edges, adds minimum non-cycle
edge.
Time Complexity O(V²) with adjacency matrix; O(E O(E log E) or O(E log V) due to
log V) with binary heap + sorting and Union-Find
adjacency list
Space O(V²) for adjacency matrix O(E) for edge list + Union-Find
Complexity arrays
Dense Graphs (E Preferred — O(V²) performs well; Less efficient — sorting O(V² log
≈ V²) fewer edges to consider V) becomes costly
Sparse Graphs Slower in naive form Preferred — few edges → fast
(E ≈ V) sort
Data Structure Priority Queue / Min-Heap Disjoint Set (Union-Find)
Cycle Detection Not needed — grows from one Needed — Union-Find detects
component cycles
Implementation Slightly complex with heap Simpler to implement
Suitable for Yes — dense city network Also suitable — when edge list is
 Parameter Prim's Algorithm Kruskal's Algorithm
SNLSN? compact

(c) Job Sequencing with Deadlines

Given jobs sorted by profit (descending):

Job Deadline Profit Rank
J1 2 100 1
J2 1 50 2
J4 1 20 3
J3 2 10 4

Algorithm: Greedily assign jobs to latest available slot before their deadline.
Max deadline = 2, so slots: [Slot 1, Slot 2]

Step Job Deadline Try Slot Result Schedule

1 J1 2 Slot 2 Assign to Slot [_, J1]
(profit=10 2
0)
2 J2 1 Slot 1 Assign to Slot [J2, J1]
(profit=50) 1
3 J4 1 Slot 1 Slot 1 [J2, J1]
(profit=20) occupied, Slot
0 N/A — SKIP
4 J3 2 Slot 2 Slot 2 [J2, J1]
(profit=10) occupied, try
Slot 1 —
occupied —
SKIP

Optimal Schedule: [J2, J1]

Maximum Profit = 50 + 100 = 150 units
Jobs J3 and J4 are excluded as all available slots were filled by higher-profit jobs.

(d) Kruskal's Algorithm – Written + Trace on Given Graph

Kruskal's Algorithm (Pseudocode):

KRUSKAL(G):
1. Sort all edges E of G in non-decreasing order of weight.
2. Initialize MST = empty set.
 3. For each vertex v ∈ V: MAKE-SET(v) // Each vertex is its own component
4. For each edge (u, v) in sorted order:
5. If FIND-SET(u) ≠ FIND-SET(v): // No cycle
6. Add (u, v) to MST
7. UNION(u, v) // Merge components
8. Return MST

Time Complexity: O(E log E) for sorting + O(E α(V)) for Union-Find ≈ O(E log E)

Trace on Given Graph (Nodes: 1,2,3,4,5,6 from the diagram):

Reading edges from the given graph diagram in Q1(d):
Edge Weight
1–2 3
1–3 9
1–4 1
2–3 3
2–4 5
3–4 2
3–6 8
4–5 3
5–2 3
5–6 7
6–2 2

Step 1: Sort edges by weight:

Order Edge Weight
1 1–4 1
2 3–4 2
3 6–2 2
4 1–2 3
5 2–3 3
6 4–5 3
7 5–2 3
8 2–4 5
9 5–6 7
10 3–6 8
11 1–3 9

Step 2: Apply Union-Find:

 Step Edge Wt Cycle? Action
1 1–4 1 No ADD → MST={1–4}
2 3–4 2 No ADD → MST={1–4,3–4}
3 6–2 2 No ADD → MST={1–4,3–
4,6–2}
4 1–2 3 No ADD → MST={1–4,3–
4,6–2,1–2}
5 2–3 3 Yes (1–4–3 and 1–2–6–2 SKIP
connected)
6 4–5 3 No ADD → MST={…,4–5}
7 5–2 3 Yes SKIP — 5 already
connected to 2 via 4–1–
2
8 2–4 5 Yes SKIP
(Don — — All 6 nodes connected MST Complete with 5
e) edges

MST Edges: 1–4(1), 3–4(2), 6–2(2), 1–2(3), 4–5(3)

Total MST Cost = 1 + 2 + 2 + 3 + 3 = 11 units

(e) Huffman Coding

Characters and frequencies: A=5, B=9, C=12, D=13, E=16, F=45

Total characters = 5+9+12+13+16+45 = 100

Step-by-Step Huffman Tree Construction:

Sort by frequency (ascending): A(5), B(9), C(12), D(13), E(16), F(45)

Step Action Result

1 Combine A(5)+B(9) Node AB(14) | Queue: C(12),D(13),AB(14),E(16),F(45)
2 Combine C(12)+D(13) Node CD(25) | Queue: AB(14),E(16),CD(25),F(45)
3 Combine AB(14)+E(16) Node ABE(30) | Queue: CD(25),ABE(30),F(45)
4 Combine CD(25)+ABE(30) Node CDBAE(55)| Queue: F(45),CDBAE(55)
5 Combine F(45)+CDBAE(55) ROOT(100)

Huffman Tree Structure (ASCII Representation):

ROOT(100)
/ \
F(45) CDBAE(55)
/ \
 CD(25) ABE(30)
/ \ / \
C(12) D(13) AB(14) E(16)
/ \
A(5) B(9)

Huffman Codes (0 = Left, 1 = Right):

Character Frequency Huffman Code Code Length (bits)
F 45 0 1
C 12 100 3
D 13 101 3
A 5 1100 4
B 9 1101 4
E 16 111 3

Bits Calculation:
Character Freq Huffman Total Huffman Fixed Bits Total Fixed Bits
Bits Bits (8)
F 45 1 45×1 = 45 8 45×8 = 360
C 12 3 12×3 = 36 8 12×8 = 96
D 13 3 13×3 = 39 8 13×8 = 104
A 5 4 5×4 = 20 8 5×8 = 40
B 9 4 9×4 = 36 8 9×8 = 72
E 16 3 16×3 = 48 8 16×8 = 128
TOTAL 100 – 224 bits – 800 bits

Fixed-length encoding total = 100 × 8 = 800 bits

Huffman encoding total = 224 bits
Bits SAVED = 800 – 224 = 576 bits
Compression Ratio = 800/224 ≈ 3.57:1 (about 72% reduction)

(f) Bellman-Ford vs Dijkstra's Algorithm & Negative Weights

Feature Dijkstra's Algorithm Bellman-Ford Algorithm

Strategy Greedy – always expands Dynamic Programming – relaxes
minimum-distance vertex all edges V-1 times
Time Complexity O((V+E) log V) with min-heap O(V×E)
Handles Negative NO – fails with negative edges YES – handles negative weights
 Feature Dijkstra's Algorithm Bellman-Ford Algorithm
Weights?
Detects Negative No Yes – if distance decreases after
Cycles? V-1 iterations
Graph Type Directed/Undirected (non- Directed graphs
negative weights)
Typical Use GPS routing, network packets Financial arbitrage, currency
exchange

Does Dijkstra Always Give Shortest Path with Negative Edges? NO.
Justification: Dijkstra's greedy choice assumes once a vertex is 'settled', its shortest distance is
finalized. With negative edges, a later-discovered path through a negative edge could produce a
shorter path to an already-settled vertex — violating the algorithm's core assumption.

Counterexample: Adding Positive Bias Fails

Claim: Add constant k to all edges to make them positive, then run Dijkstra.
Example graph G:
A --1--> B
A --4--> C
B --(-2)--> C
Actual shortest A→C = A→B→C = 1 + (-2) = -1

Add k=3 to every edge: A→B becomes 4, A→C becomes 7, B→C becomes 1
Path Original Cost After +3 per edge After Dijkstra
A→C (direct) 4 7 7
A→B→C 1+(-2)=-1 4+1=5 5
Shortest? A→B→C (-1) A→B→C (5) Correct?
For 2-edge path: actual bias added = +6 (k per edge × 2 edges)
For 1-edge path: actual bias added = +3 (k × 1 edge)
PROBLEM: The bias is per-edge, not per-path. Longer paths accumulate more bias, distorting
relative costs.
So Dijkstra on biased graph gives A→B→C = 5 (correct here), but for longer paths with more edges the
penalty grows unfairly. A path with 3 hops gets +9 bias vs 1-hop getting +3. This can reverse the
ordering of shortest paths. CONCLUSION: Adding uniform bias is INCORRECT for path comparison.

(g) Interval Scheduling Problem

Input: Set of intervals with start and finish times.

Output: Maximum subset of non-overlapping (non-conflicting) intervals.
Greedy Strategy: Always select the interval with the earliest finish time that does not conflict with
already-selected intervals. This leaves maximum room for future intervals.
 Interval Start Finish
I1 1 4
I2 3 5
I3 0 6
I4 5 7
I5 8 9
I6 5 9

Step 1: Sort by finish time: I1(1,4), I2(3,5), I4(5,7), I3(0,6), I5(8,9), I6(5,9)
Sorted: I1[1,4], I2[3,5], I4[5,7], I5[8,9] — let's sort properly:
Sorted Order Interval Start Finish
1 I1 1 4
2 I2 3 5
3 I3 0 6
4 I4 5 7
5 I6 5 9
6 I5 8 9

Step Interva Finish Last Conflict? Action

l Finish
1 I1 4 - No SELECT. last_finish=4
2 I2 5 4 Start=3 < 4: SKIP
YES
3 I3 6 4 Start=0 < 4: SKIP
YES
4 I4 7 4 Start=5 ≥ 4: SELECT. last_finish=7
NO
5 I6 9 7 Start=5 < 7: SKIP
YES
6 I5 9 7 Start=8 ≥ 7: SELECT. last_finish=9
NO

Maximum Non-Conflicting Intervals = 3: {I1[1,4], I4[5,7], I5[8,9]}

(h) Huffman Coding with Probabilities

Symbol set: {a, b, c, d, e, f} with probabilities: a=0.19, b=0.23, c=0.03, d=0.45, e=0.05, f=0.05
Total = 0.19+0.23+0.03+0.45+0.05+0.05 = 1.00 ✓
Huffman Tree Construction:
Step Merge New Node Queue State
Prob
1 c(0.03)+e(0.05) ce(0.08) f(0.05),ce(0.08),a(0.19),b(0.23),d(0.45)
2 f(0.05)+ce(0.08) fce(0.13) a(0.19),fce(0.13),b(0.23),d(0.45)
3 fce(0.13)+a(0.19) fcea(0.32) b(0.23),fcea(0.32),d(0.45)
4 b(0.23)+fcea(0.32) bfcea(0.55) d(0.45),bfcea(0.55)
5 d(0.45)+bfcea(0.55) ROOT(1.00) –

Huffman Codes:
Symbol Probability Code Length
d 0.45 0 1
b 0.23 10 2
a 0.19 110 3
f 0.05 1110 4
c 0.03 11110 5
e 0.05 11111 5

Average bits per symbol (Huffman):

= 0.45×1 + 0.23×2 + 0.19×3 + 0.05×4 + 0.03×5 + 0.05×5
= 0.45 + 0.46 + 0.57 + 0.20 + 0.15 + 0.25 = 2.08 bits/symbol

Fixed-length encoding: 6 symbols → need ⌈log₂6⌉ = 3 bits per symbol

Average bits: Fixed = 3.00 bits/symbol vs Huffman = 2.08 bits/symbol
Savings = (3.00 - 2.08)/3.00 × 100 ≈ 30.67% compression

QUESTION 2: Dynamic Programming & All-Pairs Shortest

Path

(a) Floyd-Warshall Algorithm

Algorithm Pseudocode:
FLOYD-WARSHALL(W, n):
1. D⁽⁰⁾ = W // Initialize with direct edge weights (∞ if no edge)
2. For k = 1 to n:
3. For i = 1 to n:
4. For j = 1 to n:
 5. D[i][j] = min(D[i][j], D[i][k] + D[k][j])
6. Return D

Time Complexity: O(n³) Space Complexity: O(n²)

Graph from Q2 diagram: Vertices {1,2,3}, edges: 1→2(4), 2→1(6), 1→3(11), 3→1(3), 2→3(2) [reading
from image]
Let vertices be 1,2,3. From the graph (nodes labeled 1,2,3 with weight 4 between 1-2, 11 between 1-3,
2 between 2-3, etc.):

Initial Adjacency Matrix D⁽⁰⁾:

1 2 3

1 0 4 11
2 6 0 2
3 3 ∞ 0

After k=1 (using vertex 1 as intermediate):

D[i][j] = min(D[i][j], D[i][1] + D[1][j])
D[2][3] = min(2, D[2][1]+D[1][3]) = min(2, 6+11) = min(2,17) = 2
D[3][2] = min(∞, D[3][1]+D[1][2]) = min(∞, 3+4) = 7
D⁽¹⁾ 1 2 3
1 0 4 11
2 6 0 2
3 3 7 0

After k=2 (using vertex 2 as intermediate):

D[1][3] = min(11, D[1][2]+D[2][3]) = min(11, 4+2) = 6
D[3][1]: min(3, D[3][2]+D[2][1]) = min(3, 7+6) = 3
D[1][2] unchanged. D[3][3] = 0.
D⁽²⁾ 1 2 3
1 0 4 6
2 6 0 2
3 3 7 0

After k=3 (using vertex 3 as intermediate):

D[1][2] = min(4, D[1][3]+D[3][2]) = min(4, 6+7) = 4
D[2][1] = min(6, D[2][3]+D[3][1]) = min(6, 2+3) = 5
D[1][1] = min(0, D[1][3]+D[3][1]) = min(0,6+3)=0
 D⁽³⁾ (Final) 1 2 3
1 0 4 6
2 5 0 2
3 3 7 0

Final Shortest Path Matrix D⁽³⁾ is the answer above.

(b) Shortest Route Analysis

From the final matrix:

Path Shortest Distance Route
1→2 4 Direct: 1→2
1→3 6 Via 2: 1→2→3 (4+2=6)
2→1 5 Via 3: 2→3→1 (2+3=5)
2→3 2 Direct: 2→3
3→1 3 Direct: 3→1
3→2 7 Via 1: 3→1→2 (3+4=7)

(c) Introducing Negative Edge: C→D = -2 (Adapted to Graph)

If we introduce a negative edge (e.g., 3→2 = -3) making D[3][2] = -3:

Updated D⁽⁰⁾ 1 2 3
1 0 4 11
2 6 0 2
3 3 -3 0

After running Floyd-Warshall, shortest paths change:

D[1][2] = min(4, 1→3→2 = 11+(-3)=8) → still 4
D[2][2] = min(0, 2→3→2 = 2+(-3)=-1) → -1 indicates NEGATIVE CYCLE!
Important: If D[i][i] < 0 for any i after Floyd-Warshall, a negative cycle exists. Floyd-Warshall is
INCORRECT for graphs with negative cycles — shortest paths become undefined (can loop
infinitely to reduce cost).
Without negative cycles, Floyd-Warshall correctly handles negative edge weights (unlike Dijkstra).

QUESTION 3: Resource Optimization – Knapsack + TSP

(a) 0/1 Knapsack Problem

Capacity W = 10, Items: I1(wt=2,val=20), I2(wt=3,val=30), I3(wt=5,val=50), I4(wt=7,val=70)

DP Recurrence:
dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) if w ≥ wt[i]
dp[i][w] = dp[i-1][w] if w < wt[i]

DP Table (rows = items, columns = capacity 0 to 10):

Item \ Cap 0 1 2 3 4 5 6 7 8 9 10
0 (none) 0 0 0 0 0 0 0 0 0 0 0
I1(w=2,v= 0 0 20 20 20 20 20 20 20 20 20
20)
I2(w=3,v= 0 0 20 30 30 50 50 50 50 50 50
30)
I3(w=5,v= 0 0 20 30 30 50 50 70 80 80 100
50)
I4(w=7,v= 0 0 20 30 30 50 50 70 80 90 100
70)

Backtracking to Find Selected Items:

dp[4][10] = 100. Check: was I4 included?
dp[3][10]=100 = dp[4][10], so I4 NOT included.
dp[3][10]=100. Check: was I3 included?
dp[2][10]=50 ≠ 100, and dp[2][10-5]+50 = dp[2][5]+50 = 50+50=100 ✓ → I3 INCLUDED. Remaining
cap = 5.
dp[2][5]=50. Check: was I2 included?
dp[1][5]=20 ≠ 50, dp[1][5-3]+30 = dp[1][2]+30 = 20+30=50 ✓ → I2 INCLUDED. Remaining cap = 2.
dp[1][2]=20. Check: was I1 included?
dp[0][0]=0 ≠ 20. dp[0][2-2]+20 = 0+20=20 ✓ → I1 INCLUDED.

Selected Items: I1(wt=2,val=20) + I2(wt=3,val=30) + I3(wt=5,val=50)

Total Weight = 2+3+5 = 10 ✓ | Total Value = 20+30+50 = 100

(b) Travelling Salesman Problem – Held-Karp DP

Cost matrix for the TSP graph (from Q3 diagram, cities 1,2,3,4):
From \ To 1 2 3 4
1 0 10 15 20
 From \ To 1 2 3 4
2 10 0 25 30
3 15 25 0 35
4 20 30 35 0

Held-Karp DP:
Let dp[S][i] = minimum cost to reach city i, having visited exactly the cities in set S, starting from city 1.
S = subset of cities (bitmask), i = current city.
Base case: dp[{1}][1] = 0
Transition: dp[S ∪ {j}][j] = min(dp[S][i] + cost[i][j]) for all i ∈ S, j ∉ S
Final answer: min over all i: dp[{all cities}][i] + cost[i][1]

Trace (cities 1,2,3,4, start=1):

State S Current City i dp[S][i] Computed From
{1} 1 0 Start
{1,2} 2 10 dp[{1}][1]+cost[1][2]=0+10=10
{1,3} 3 15 dp[{1}][1]+cost[1][3]=0+15=15
{1,4} 4 20 dp[{1}][1]+cost[1][4]=0+20=20
{1,2,3} 3 35 dp[{1,2}][2]+cost[2][3]=10+25=35
{1,2,4} 4 40 dp[{1,2}][2]+cost[2][4]=10+30=40
{1,3,4} 4 50 dp[{1,3}][3]+cost[3][4]=15+35=50
{1,2,3} 2 40 dp[{1,3}][3]+cost[3][2]=15+25=40 → keep 35
{1,2,3,4} 4 70 min(dp[{1,2,3}][3]+cost[3][4],dp[{1,2,3}]
[2]+cost[2][4])=min(35+35,35+30)=min(70,65)
{1,2,3,4} 4 (via 2→4) 65 dp[{1,2,3}][2]+cost[2][4]=35+30=65
{1,2,3,4} 3 (via 4→3) 75 dp[{1,2,4}][4]+cost[4][3]=40+35=75
{1,2,3,4} 2 (via all) 85 dp[{1,3,4}][4]+cost[4][2]=50+30=80

Return to start (city 1):

Optimal tour ending at 2: dp[all][2]+cost[2][1] = check all...
Tour 1→2→3→4→1: 10+25+35+20 = 90
Tour 1→2→4→3→1: 10+30+35+15 = 90
Tour 1→3→2→4→1: 15+25+30+20 = 90
Minimum TSP Tour Cost = 80 units
Optimal Path: 1 → 2 → 3 → 4 → 1 (or equivalent route with cost 80)
(c) TSP on Given Graph (Start = Vertex 1)

From the graph image in Q3: Vertices 1,2,3,4 with edges:

1–2: 10, 1–3: 15 (via 4), 1–4: 20, 2–3: 25, 2–4: 30, 3–4: 35
(Alternatively reading from diagram: 1→2=10, 1→4=20, 2→4=25, 2→3=30, 3→4=35, 1→3=15)
Tour Path Total Cost
Tour 1 1→2→3→4→1 10+30+35+20=95
Tour 2 1→2→4→3→1 10+25+35+15=85
Tour 3 1→3→2→4→1 15+30+25+20=90
Tour 4 1→3→4→2→1 15+35+25+10=85
Tour 5 1→4→2→3→1 20+25+30+15=90
Tour 6 1→4→3→2→1 20+35+30+10=95
Minimum Cost Tour = 85 units (Tour 2 or Tour 4)
Optimal Path: 1 → 2 → 4 → 3 → 1 or 1 → 3 → 4 → 2 → 1

QUESTION 4: LCS & Optimal BST

(a) Longest Common Subsequence (LCS)

S1 = ABCDGH (length m=6)

S2 = AEDFHR (length n=6)

LCS DP Table:
dp[i][j] = length of LCS of S1[1..i] and S2[1..j]
If S1[i]==S2[j]: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ε A E D F H R

ε 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3
LCS Length = 3
Traceback: dp[6][6]=3, S1[6]=H=S2[5]=H → H is in LCS, go to dp[5][4]
dp[5][4]=2, S1[5]=G≠S2[4]=F, dp[4][4]=2=dp[5][3]=2 → go up: dp[4][4]=2
S1[4]=D=S2[3]=D → D is in LCS, go to dp[3][2]
dp[3][2]=1, S1[3]=C≠S2[2]=E, S1[2]=B≠S2[2]=E, S1[1]=A=S2[1]=A → A is in LCS
LCS = ADH (Length = 3)

(b) Optimal Binary Search Tree (OBST)

Keys: K1(p=0.2), K2(p=0.5), K3(p=0.3)

No dummy keys considered (simplified version as given).

OBST DP Table Construction:

cost[i][j] = minimum expected search cost for keys Ki..Kj
w[i][j] = sum of probabilities for keys Ki..Kj
root[i][j] = root that minimizes cost[i][j]

Base Cases (single keys):

Subproblem w[i][j] cost[i][j] root[i][j]
cost[1][1] 0.2 0.2 K1
cost[2][2] 0.5 0.5 K2
cost[3][3] 0.3 0.3 K3

Length 2 subproblems:
cost[1][2]: Try K1 as root: cost[0][0]+cost[2][2]+w[1][2] = 0+0.5+0.7=1.2
Try K2 as root: cost[1][1]+cost[3][3 is out]+w[1][2] = 0.2+0+0.7=0.9
min = 0.9, root = K2
cost[2][3]: Try K2 as root: 0+0.3+0.8=1.1
Try K3 as root: 0.5+0+0.8=1.3
min = 1.1, root = K2
Subproblem w[i][j] cost[i][j] root[i][j]
cost[1][2] 0.7 0.9 K2
cost[2][3] 0.8 1.1 K2

Full tree cost[1][3]:

Try K1 as root: cost[0][0]+cost[2][3]+w[1][3] = 0+1.1+1.0 = 2.1
Try K2 as root: cost[1][1]+cost[3][3]+w[1][3] = 0.2+0.3+1.0 = 1.5
Try K3 as root: cost[1][2]+cost[4][3]+w[1][3] = 0.9+0+1.0 = 1.9
min = 1.5, root = K2

Optimal BST Cost = 1.5

Root = K2 (probability 0.5)
Left subtree of K2: K1 (leaf)
Right subtree of K2: K3 (leaf)

Final OBST Structure:

K2 (root, p=0.5)
/ \
K1 K3
(p=0.2) (p=0.3)

Verification: E[cost] = 0.5×1 + 0.2×2 + 0.3×2 = 0.5+0.4+0.6 = 1.5 ✓

QUESTION 5: NP-Completeness & Approximation

(a) Vertex Cover Problem – NP & NP-Completeness Proof

Definition: A Vertex Cover of graph G=(V,E) is a subset S ⊆ V such that for every edge (u,v) ∈ E,
at least one of u or v is in S. The decision problem: Does G have a vertex cover of size ≤ k?

Part 1: Vertex Cover ∈ NP

To show a problem is in NP, we must show a certificate can be verified in polynomial time.
Certificate: A subset S of vertices claimed to be a vertex cover of size ≤ k.
Verification Algorithm:
1. Check |S| ≤ k → O(1)
2. For every edge (u,v) ∈ E, check u ∈ S OR v ∈ S → O(|E|)
Total verification time: O(|E|) = Polynomial ✓ → Vertex Cover ∈ NP

Part 2: Vertex Cover is NP-Complete (Reduction from Independent Set)

We reduce the known NP-Complete problem INDEPENDENT SET to VERTEX COVER.
Claim: G has an Independent Set of size k ⟺ G has a Vertex Cover of size n-k (where n=|V|)
Proof:
(⇒) Let I be an independent set of size k. Let S = V\I (size n-k).
For any edge (u,v) ∈ E: since I is independent, u and v cannot both be in I.
So at least one of u,v must be in V\I = S. Hence S is a vertex cover of size n-k.
(⇐) Let S be a vertex cover of size n-k. Let I = V\S (size k).
For any two vertices u,v ∈ I: suppose edge (u,v) exists. Then neither u nor v is in S,
contradicting S being a vertex cover. So no edge exists between vertices of I → I is an independent set.
Since Independent Set is NP-Complete and reduces to Vertex Cover in polynomial time →
Vertex Cover is NP-Complete ✓

(b) Approximate Vertex Cover (Greedy)

Graph: V={A,B,C,D,E}, E={(A,B),(A,C),(B,C),(C,D),(D,E)}

Greedy Approximation Algorithm:

Repeatedly pick any uncovered edge (u,v), add BOTH u and v to cover, remove all edges incident to u
or v.
Step Edge Picked Vertices Remaining Edges
Added
1 (A,B) A, B {(C,D),(D,E)} — (A,C),(B,C) removed as A,B covered
2 (C,D) C, D {} — (D,E) removed as D covered
Done – – All edges covered

Approximate Vertex Cover = {A, B, C, D} (size = 4)

Optimal Solution:
Check {A,C,D}: covers (A,B)? → A✓, (A,C)? → A✓ or C✓, (B,C)? → C✓, (C,D)? → C ✓ or D ✓, (D,E)?
→ D✓
Optimal Vertex Cover = {A, C, D} (size = 3)

Approach Cover Size Notes

Greedy Approx. { A, B, C, D } 4 2-approximation guarantee
Optimal { A, C, D } 3 Minimum possible
The greedy 2-approximation is guaranteed to give a cover ≤ 2 × OPT. Here 4 ≤ 2×3=6 ✓

(c) P, NP, NP-Complete, NP-Hard – Definitions & Examples

Class Definition Real-World Example from SNLSN

P Problems solvable in Shortest path (Dijkstra) — finds optimal route in
polynomial time O(nᵏ) O(E log V). MST (Prim/Kruskal) — O(E log E).
by deterministic
algorithm.
NP Problems verifiable in Checking if a given delivery route visits all cities
polynomial time. exactly once and has cost ≤ k is O(n) to verify.
Solutions can be
 Class Definition Real-World Example from SNLSN
checked quickly, but
may not be found
quickly.
NP- Problems in NP that TSP Decision: Is there a tour ≤ cost k? Vertex
Complete every NP problem can Cover: Can all roads be monitored with ≤ k
be reduced to in stations?
polynomial time.
Hardest problems in
NP.
NP-Hard At least as hard as Optimization TSP: Find the MINIMUM cost tour.
NP-Complete. May not Not in NP (we can't verify a claimed minimum
be in NP (not without solving the problem).
necessarily verifiable
in poly time).

Key Relationships:
P ⊆ NP ⊆ NP-Hard
NP-Complete = NP ∩ NP-Hard
P = NP? → Greatest unsolved problem in computer science
If any NP-Complete problem is in P, then P = NP (all NP problems become
polynomial)

(d) Decision Problems vs Optimization Problems

Feature Decision Problem Optimization Problem

Output YES or NO answer A value (minimum/maximum) or
optimal solution
Form 'Is there a solution satisfying 'What is the best/optimal
condition X?' solution?'
Complexity Used to classify NP- Usually NP-Hard (harder than
Completeness corresponding decision)
TSP Example Is there a tour with cost ≤ k? Find the minimum cost
(YES/NO) Hamiltonian tour.
Knapsack Can we achieve profit ≥ P with Maximize profit subject to weight
Example weight ≤ W? (YES/NO) constraint W.
Vertex Cover Does graph G have a vertex Find the smallest vertex cover of
cover of size ≤ k? G.
Relationship Decision ≤ Optimization Optimization ≥ Decision in
(optimization solves decision) complexity
Every optimization problem has a corresponding decision version. If the optimization problem is easy
(polynomial), so is the decision version. NP-Completeness is defined for decision problems because
YES/NO answers are easier to work with mathematically (certificates can be verified).

(e) SAT and NP-Hardness – Cook's Theorem

Satisfiability (SAT): Given a Boolean formula φ, is there an assignment of TRUE/FALSE to

variables that makes φ TRUE?

Cook's Theorem (1971): SAT is NP-Complete.

This is the foundational result for NP-Completeness theory.

How SAT Proves Other Problems are NP-Hard:

To prove problem X is NP-Hard:
1. Show SAT (or another known NP-Complete problem) ≤_p X (polynomial reduction)
2. Construct a mapping: any SAT instance → instance of X, in polynomial time
3. Show: SAT is satisfiable ⟺ X has a solution
4. Since SAT (NP-Complete) reduces to X, X is at least as hard → X is NP-Hard

Example: Proving 3-SAT ≤_p Independent Set (IS)

3-SAT: Formula with clauses, each with exactly 3 literals. Is it satisfiable?
Construction: For each clause (l₁ ∨ l₂ ∨ l₃), create a triangle (3 vertices: l₁, l₂, l₃).
Add conflict edges: between a literal and its negation across triangles.
Formula is satisfiable ⟺ Graph has Independent Set of size = number of clauses.
Implication: Since 3-SAT ≤_p IS, Independent Set is NP-Hard. Since IS ∈ NP, IS is NP-Complete.
Similarly: IS ≤_p Vertex Cover, TSP, Hamiltonian Cycle, etc. — creating a web of NP-Complete
problems.

(f) 3-SAT Formula → Independent Set Instance

Given Formula: φ = (¬x₁ ∨ x₂ ∨ x₃) ∧ (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₃)

Reduction Construction (Karp Reduction):

Step 1: For each clause Cᵢ with literals (l¹ᵢ, l²ᵢ, l³ᵢ), create 3 vertices: vᵢ₁, vᵢ₂, vᵢ₃.
Step 2: Connect all vertices within the same clause (triangle edges) → forces at most 1 vertex selected
per clause.
Step 3: Add conflict edges between v and w if v = xⱼ and w = ¬xⱼ (or vice versa) across different clauses.
Vertices Created:
Clause Literal 1 (v₁) Literal 2 (v₂) Literal 3 (v₃)
C₁: (¬x₁∨x₂∨x₃) v₁₁ = ¬x₁ v₁₂ = x₂ v₁₃ = x₃
C₂: (x₁∨¬x₂∨x₃) v₂₁ = x₁ v₂₂ = ¬x₂ v₂₃ = x₃
C₃: (¬x₁∨x₂∨x₃) v₃₁ = ¬x₁ v₃₂ = x₂ v₃₃ = x₃

Edges:
Triangle edges (within each clause):
C₁: (v₁₁,v₁₂), (v₁₁,v₁₃), (v₁₂,v₁₃)
C₂: (v₂₁,v₂₂), (v₂₁,v₂₃), (v₂₂,v₂₃)
C₃: (v₃₁,v₃₂), (v₃₁,v₃₃), (v₃₂,v₃₃)

Conflict edges (between complementary literals across clauses):

v₁₁(¬x₁) — v₂₁(x₁): conflict
v₁₂(x₂) — v₂₂(¬x₂): conflict
v₂₁(x₁) — v₃₁(¬x₁): conflict
v₂₂(¬x₂) — v₃₂(x₂): conflict

Claim: φ is satisfiable ⟺ the constructed graph has an Independent Set of size k=3 (one per
clause).
Proof sketch: Assign x₁=FALSE, x₂=TRUE, x₃=TRUE.
C₁: ¬x₁=T → v₁₁ selected; C₂: x₃=T → v₂₃ selected; C₃: x₂=T → v₃₂ selected.
{v₁₁, v₂₃, v₃₂}: No two share a triangle (different clauses). No conflict edges between them.
→ {v₁₁, v₂₃, v₃₂} is a valid Independent Set of size 3. Formula is satisfiable. ✓

END OF ASSIGNMENT SOLUTION – Design & Analysis of Algorithms