PART A

1. B
2. B
3. D
4. B
5. C
6. A
7. C
8. C

9. Knapsack Capacity: 5 units

Number of Items: 3
Weights: w = [2, 3, 4]
Profits: p = [40, 50, 65]

Item 3 is selected that fits to the max of Knapsack bag => Max Profit = 65

Optimal approach

Item ↓ / Capacity → 0 1 2 3 4 5

0 items 0 0 0 0 0 0

Item 1 0 0 40 40 40 40

Item 2 0 0 40 50 50 90

Item 3 0 0 40 50 65 90

{Item 1, Item 2} are selected that fits to the capacity of Knapsack bag (M =5)
yielding the maximum optimum profit 90
 10. In the following graph, classify whether each of the following sequences is a DFS
or not. Justify your claim ONLY in case of INVALID DFS ordering.

Sequence Valid DFS? Justification if Invalid

(a) MNOPQR Yes —

(b) NQMPOR No M to P is invalid (M is not connected to P)

(c) QMNPRO No R to O is invalid (R and O are not connected)

(d) QMNPOR No O to R is invalid (no edge between O and R)

(e) NQPOMR Yes —

11. a) Recurrence relation when at most q ≤ 2 elements are less than the pivot at every
step T(n)=T(q)+T(n−q−1) + O(n)
Since q is constant (≤ 2): T(n)=T(n−3) + O(n)
(b) Recurrence relation when pivot always splits the array equally (n/2 elements < pivot)
This implies the pivot divides the array exactly into two equal halves (best/average case):
T(n)=2T(n/2) + O(n)
c) Time Complexity for both cases
1. Case (a): T(n) = T (n – 3) + O(n)
Time Complexity: O(n²)
2. Case (b): T(n) = 2T(n/2) + O(n)
Time Complexity: O (n log n)
d)
 12
A) LCS(p,q)=1+LCS (p−1, q−1)
B) LCS(p,q)=max (LCS (p−1, q), LCS (p, q−1))
C)

D) LCS (4, 6) = 4 gives the full LCS between Y = "GACT" and X = "ACCGAT"
E) LCS (0, q) = 0: No common subsequence between empty X and any prefix of Y.
LCS (p, 0) = 0: No common subsequence between any prefix of X and empty Y.
They signify that the LCS involving an empty string is always 0.
F) Longest Common Subsequence (LCS): GCAT
Length of LCS: 4
G) Length of LCS: 3
One possible LCS: (from earlier trace structure) → GCA or ACA

12 B)
Character Frequency

p 5

e 5

t 1

r 3

(space) 3

i 2

c 2

k 1

d 1

s 1
 [24] root
/ \
[14] [10]
/ \ / \
[6] [8] [p:5] [e:5]
/ \ / \
[r:3] [ :3] [4] [4]
/\ /\
[tk:2][ds:2][i:2][c:2]
/\ /\
[t:1][k:1][d:1][s:1]

Character Frequency Huffman Code

t 1 00000

k 1 00001

d 1 00010

s 1 00011

i 2 0010

c 2 0011

r 3 010

(space) 3 011

p 5 10

e 5 11
 Character Huffman Code

p 10

e 11

c 0011

k 00001

e 11

d 00010

(space) 011

s 00011

i 0010

s 00011

t 00000

e 11

r 010

13. A)
Flower Positions (row, column):
(1,1), (2,4), (3,2), (4,5), (5,3)

Flower Positions (row, column):

(1,1), (2,3), (3,5), (4,2), (5,4)

Flower Positions (row, column):

(1,2), (2,4), (3,1), (4,3), (5,5)

• At each level, there are at most M choices.

• Depth of recursion = M (5 rows).
Worst-case complexity: O (M!)

13 B)
Function TSP_BnB(graph, N):
min_cost ← ∞
best_path ← []

Function is_promising(curr_cost, min_cost):

return curr_cost < min_cost

Function BnB(curr_city, visited, curr_path, curr_cost):

if length(curr_path) == N:
if graph[curr_city][0] > 0: // Check return path to start
 total_cost ← curr_cost + graph[curr_city][0]
if total_cost < min_cost:
min_cost ← total_cost
best_path ← copy of curr_path + [0]
return

for next_city in 0 to N-1:

if not visited[next_city] and graph[curr_city][next_city] > 0:
next_cost ← curr_cost + graph[curr_city][next_city]

if is_promising(next_cost, min_cost):
visited[next_city] ← True
BnB(next_city, visited, curr_path + [next_city], next_cost)
visited[next_city] ← False // backtrack

// Initialization
visited ← array of N False
visited[0] ← True // start at city 0
BnB(0, visited, [0], 0)

return min_cost, best_path

Route Total Distance

0→1→2→3→0 10 + 35 + 30 + 20 = 95

0→1→3→2→0 10 + 25 + 30 + 15 = 80

0→2→1→3→0 15 + 35 + 25 + 20 = 95

0→2→3→1→0 15 + 30 + 25 + 10 = 80

0→3→1→2→0 20 + 25 + 35 + 15 = 95

0→3→2→1→0 20 + 30 + 35 + 10 = 95

Worst case: O(n!)

14 A)
Define Vertex Cover of a Graph (1 mark)
A vertex cover of a graph is a set of vertices such that every edge in the graph has at
least one of its endpoints in the set.

Provide a Vertex Cover of Size 4 for G (1 mark)

One valid vertex cover of size 4 is:
{c,a,b,f} / {c,a,d,f}

What is the size of a minimum vertex cover of G? (1 mark)

{c,d,f}(Size = 3)

What is the size of a maximum vertex cover of G? (1 mark)

The maximum vertex cover includes all vertices (worst case):
Total vertices = 6
Is the set {a, c, f} a vertex cover of G? Justify your claim. (2 marks)
Set = {a, c, f}
No, {a ,c,f} is not a vertex cover since edge (d, e) is not covered

Is the problem of finding a vertex cover of size at most k in a graph in class NP?
(3 marks)
Yes, the vertex cover decision problem is in NP class.
Given a graph G=(V,E) and integer k, the problem asks:
“Is there a vertex cover of size at most k?"
This problem is in NP because:
o A solution (certificate) is a set of vertices S⊆V, with ∣S∣≤k|.
o We can verify in polynomial time whether S is a valid vertex cover:
▪ For each edge (u,v)∈E\in E(u,v)∈E, check whether u∈S or v∈S.
▪ This takes O(∣E∣) time.
Yes, Vertex Cover is in NP since given a candidate set, we can verify it in polynomial
time
14 B)

When do you say a problem A is in class NP-Complete? (2 marks)

A problem A is said to be NP-Complete if it satisfies both the following conditions:

1. A ∈ NP:
A solution to the problem can be verified in polynomial time by a non-deterministic
Turing machine.

2. NP-Hardness:
Every problem in NP can be polynomially reduced to problem A

i.e., ∀B ∈ NP,

i. Determining if there exists an independent set of size at least k in a graph (2 marks)

Yes, this problem is in NP

To verify, check that:

o No two vertices in S share an edge.

o |S| ≥ k.

• Both steps can be verified in polynomial time.

Yes, in NP.

Finding a maximum independent set of a graph (2 marks)

No, this problem is not known to be in NP

• This is an optimization problem, not a decision problem.

• NP class is defined for decision problems.

• The decision version (e.g., "Is there an independent set of size ≥ k?") is in NP, but
finding the actual maximum is not verifiable in poly time unless P=NP.

No, not in NP (optimization problem)

 iii) Determining whether a graph has a Hamiltonian Cycle (2 marks)
Yes, this problem is in NP
To verify, check:
o The cycle includes each vertex exactly once.
o There exists an edge between each pair of consecutive vertices in the cycle,
and from last to first.
• This verification can be done in polynomial time.
Yes, in NP.