SRM Institute of Science and Technology

College of Engineering and Technology

School of Computing
SRM Nagar, Kattankulathur - 603203, Chenglpattu District, Tamilnadu
Academic Year 2024-2025(EVEN)
SET C
Test: FJ III Date: 30-04-2025
Course Code & Title: 21CSC204J & Design and Analysis of Algorithms
Duration: 1 hour 40 minutes
Year & Sem: II Year / IV Sem Maximum Marks: 50
Part A (Multiple Choice Questions) 8*1=8 marks
1.(b) -4
2. (b)- T has n edges
3. (a)- 3
4. (d) - 0
5. (c)- O(n³)
6. (a) -3n
7. (b)- Only B
8. (b)- Θ(n + m)

21CSC201J- Datastrucutres and Algorithms -CT2-SET C - Part B

9. Let us assume we have these 3 objects:

Object Weight Profit

1 2 90

2 3 100

3 4 120

Knapsack capacity = 5
Now, according to the strategy: pick the object with the highest profit:
1. Highest profit is 120 (object 3, weight 4).
o It fits (capacity 5 ≥ 4), so we pick object 3 fully.
o Remaining capacity = 5 - 4 = 1.
 2. Now, pick the next highest profit object: object 2 (profit 100, weight 3).
o 3 > 1 → it doesn't fully fit. So, we take a fraction:
 Fraction = 1/3 of object 2.
 Profit gained = (1/3) × 100 = 33.33.
Thus, total profit using the given strategy:
 Profit from object 3 = 120
 Profit from fraction of object 2 = 33.33
 Total = 153.33
let's find the optimal solution (using profit/weight ratio):

Object Weight Profit Profit/Weight

1 2 90 45

2 3 100 33.33

3 4 120 30

Highest profit/weight ratio is object 1 (45), then object 2 (33.33), then object 3 (30).
Thus, optimal way:
1. Pick object 1 fully (weight 2, profit 90).
o Remaining capacity = 5 - 2 = 3.
2. Pick object 2 fully (weight 3, profit 100).
o Remaining capacity = 3 - 3 = 0.
No capacity left.
Thus, total optimal profit = 90 + 100 = 190.

Strategy Subset picked Total Profit

"Max profit first" strategy Full object 3 + 1/3 object 2 153.33

Optimal (profit/weight greedy) Full object 1 + full object 2 190

10. Steps to Find Level-k Friends Using BFS

1. Initialize:
o A queue to manage nodes to visit (e.g., queue = [1]).
o A dictionary or array to keep track of the level of each node (e.g., level[1] = 0).
o A visited set to prevent revisiting.
2. Traverse using BFS:
o For each node dequeued, check its unvisited neighbors.
 o For each neighbor:
 Mark it visited.
 Assign level[neighbor] = level[current_node] + 1.
 Add it to the queue.
3. Group nodes by level:
o Store nodes in lists according to their level.
o For example: level_1 = [2,6,8], level_2 = [3,7,9], etc.
Starting at Node 1, the BFS levels look like:
 Level 0: 1
 Level 1: 2, 6, 8
 Level 2: 3, 7, 9
 Level 3: 4, 5

11. Hiring Problem

i. Candidates arrive in non-decreasing order of skills
Goal: Interview n candidates and hire the best m of them.
 Since the candidates are sorted in increasing skill, the last m candidates are the
best.

 Mr. ABC interviews all n candidates, so total interview cost =

 He hires the last m candidates, so total hiring cost =

Total Cost = Interview cost + hiring Cost

ii. Candidates arrive in random order, and decision must be made immediately
Rule: Mr. ABC hires a candidate only if they are the best so far.
(This is similar to the classical "Online Hiring Problem" or "Secretary Problem"
approach.)

 He interviews all n candidates, so total interview cost =

  A candidate is hired only if they are better than all previous ones.
So, Mr. ABC ends up hiring all the record-breaking candidates (each new "best-so-
far").
 In expectation, the number of such record-breaking candidates is approximately:

 If Mr. ABC wants to hire exactly m best candidates, this strategy is not guaranteed
to get the top m, but he hires only those who are better than all seen so far.
Suppose this ends up being k hires.
Let the indices of hired candidates be i1,i2,...,ik, where k≤m
Total Cost=

12 a) i)

ii)

III)

iv)
 opt(0, W) = 0: If no items are available, profit is 0 regardless of capacity.
 opt(n, 0) = 0: If knapsack capacity is 0, we can't include any item, so profit is 0.
v)
Determine items for capacity = 8 using the table
From the table (last cell bottom-right):
🔹 Maximum profit = 8 at opt(4, 8)

To find which items were included:

 Start at opt(4, 8) = 8
  Compare with opt(3, 8) = 7 → different ⇒ item 4 was included
o Subtract weight of item 4 → 8 − 5 = 3
 Move to opt(3, 3) = 2, compare with opt(2, 3) = 2 → same ⇒ item 3 not included
 Move to opt(2, 3) = 2, compare with opt(1, 3) = 1 ⇒ item 2 was included
o Subtract weight 3 → 3 − 3 = 0
Items included:
 Item 2 (profit 2, weight 3)
 Item 4 (profit 6, weight 5)
Total weight = 3 + 5 = 8
Total profit = 2 + 6 = 8
vi) Knapsack capacity reduced to 6, item 4 removed
Now use only items 1, 2, and 3 (profits: 1, 2, 5; weights: 2, 3, 4)
From row 3 (3 items), column 6:
 opt(3, 6) = 7
To trace:
 opt(3, 6) = 7, opt(2, 6) = 3 ⇒ item 3 included (weight 4), capacity left = 2
 opt(2, 2) = 1, opt(1, 2) = 1 ⇒ item 2 not included
 opt(1, 2) = 1, opt(0, 2) = 0 ⇒ item 1 included (weight 2)
Items included:
 Item 1 (profit 1, weight 2)
 Item 3 (profit 5, weight 4)
Total weight = 2 + 4 = 6
Total profit = 6
Vii) Complexity-= O(n⋅W)

12 b) OBST
Let
 n = 5 (number of employees)
 p[i] = probability of employee i being searched
 cost[i][j] = minimum cost of searching keys from i to j
 root[i][j] = root key index for optimal subtree from i to j
Steps (Summarized):
1. Initialize cost[i][i] = p[i] for all i
2. For all lengths l = 2 to n:
o For all i = 1 to n - l + 1:
 Set j = i + l - 1
 For all possible roots r = i to j:
 Compute cost = left subtree + right subtree + sum of
probabilities from i to j
 Store the minimum in cost[i][j]
Minimum Expected Cost of Search: 1.8

13 a)
 Items:
V = {10, 10, 12, 18}
w = {2, 4, 6, 9}
 Knapsack Capacity (W) = 15

Step 1: Sort Items by Value-to-Weight Ratio

Item Value Weight V/W

1 10 2 5.0

2 12 6 2.0

3 10 4 2.5

4 18 9 2.0

Sorted order by value density:

Item 1, Item 3, Item 2, Item 4
So we now refer to:
 V = {10, 10, 12, 18}
 w = {2, 4, 6, 9} (reordered)
Step 2: Branch and Bound Tree
Each node represents a state: (level, profit, weight, bound)
1. Root Node
Level 0: (0, 0, 0, Bound = 36.67)
o Bound is computed by adding fractions of next items to capacity
Bound Calculation Formula:
For a node at level l, with current weight w and profit p:
 Add items greedily by value/weight until capacity W
 If item can't fit completely, add fractional value to estimate
Step 3: Branches from Root (Include/Exclude Items)
Node A (Include Item 1)
 (level=1, profit=10, weight=2)
 Bound = 10 + 10 + 12 + (3/9 * 18) = 10 + 10 + 12 + 6 = 38
Node B (Exclude Item 1)
  (level=1, profit=0, weight=0)
 Bound = 10 + 12 + 18 = 40

✔ Node A and B are both feasible → we explore them further

Exploring Node A
Include Item 3
 Profit = 10 + 10 = 20
 Weight = 2 + 4 = 6
 Bound = 20 + 12 + (7/9 * 18) = 20 + 12 + 14 = 46 → promising
Exclude Item 3
 Profit = 10
 Weight = 2
 Bound = 10 + 12 + 18 = 40
Continue to next levels similarly...
Pruning
At each level, if bound ≤ current max profit, we prune the branch.
For example, if we already found a complete solution of profit 38, we won't explore any node
whose bound ≤ 38.
Optimal Path
Let’s trace a valid high-profit path:
1. Include Item 1 (V=10, w=2)
2. Include Item 3 (V=10, w=4 → total 6)
3. Include Item 2 (V=12, w=6 → total 12)
4. Exclude Item 4 (would exceed capacity)
Total value: 10 + 10 + 12 = 32, total weight = 12
We can fit Item 1, 3, and 2 in the knapsack.
Answer
 Selected Items: 1, 3, 2
 Total Profit: 32
 Total Weight: 12 ≤ 15
 Unexplored paths: Pruned due to low bound estimates
13 b Shortest path algorithm

[Link] Path Algorithm

Dijkstra’s Algorithm can be used
(OR)
Floyd Warshall’s Algorithm can be used
Marks can be awarded for both methods
Shortest distance:

H  H1 = 30 (H  H2  H1)

H  H2 = 20 (H  H2)

H  H3 = 35 (H  H3)

H  H4 = 25 (H  H4)

H  H5 = 35 (H  H5)
ii. H3 and H5 are farthest from the patient home with a cost of 35
14 a)
i. Independent Set in Graph G
Given that the subset {v2,v3,v5} is a vertex cover of graph GGG, this means that every edge
in GGG must be incident to at least one of the vertices in {v2,v3,v5}. The independent set is
a set of vertices in which no two vertices are adjacent.
To identify an independent set:
 Any vertex that is not part of the vertex cover and is not adjacent to any vertex in the
vertex cover can form part of the independent set.
So, the independent set must be a subset of vertices that are neither in {v2,v3,v5} nor
adjacent to them.
In this case, {v1,v4,v6} could form an independent set if none of these vertices are adjacent
to each other or to any of the vertices in the vertex cover. Justification: Since {v2,v3,v5} is a
vertex cover, all edges are covered by those vertices, and no edges should exist between
the vertices {v1,v4,v6}.
ii. NP-Complete Problem Definition
A problem AAA is in class NP-complete if:
1. AAA is in NP, meaning a solution to the problem can be verified in polynomial time.
2. Every problem in NP can be reduced to AAA in polynomial time (i.e., AAA is NP-
hard).
Example of an NP-complete problem: The Travelling Salesman Problem (TSP), where
the goal is to find the shortest possible route that visits each city exactly once and returns to
the origin city. This problem is both in NP (as the validity of a solution can be verified in
polynomial time) and NP-hard (since any problem in NP can be reduced to TSP in
polynomial time).
iii. Venn Diagram for P, NP, NP-Hard, and NP-Complete
Assuming P≠NP, the relationships among the complexity classes can be depicted in the
following way:
 P is a subset of NP.
 NP-Complete is a subset of NP.
 NP-Hard includes NP-Complete but can also include problems that are not in NP.
Here’s how to depict it:
1. Draw a large rectangle for NP-Hard.
2. Inside NP-Hard, draw a smaller rectangle for NP-Complete.
3. Inside NP, but not necessarily touching NP-Hard, draw a rectangle for P.
So, you have:
 P ⊆ NP.
 NP-Complete ⊆ NP ⊆ NP-Hard.
  NP-Complete ⊆ NP-Hard, but not every NP-Hard problem is in NP.
iv. Vertex Cover Problem in NP
The Vertex Cover Problem is the problem of determining whether there exists a vertex
cover of size at most kkk in a given graph.
To show that the Vertex Cover Problem is in NP:
1. Verification in Polynomial Time: Given a candidate vertex cover of size at most
kkk, we can verify whether it is a valid vertex cover by checking if every edge in the
graph is incident to at least one vertex in the given set. This can be done in
polynomial time by scanning through all the edges and ensuring that each edge is
covered by at least one vertex in the proposed set.
2. Algorithm: The verification step involves iterating over all edges in the graph, which
can be done in polynomial time with respect to the number of vertices and edges.
Since a proposed solution (a set of kkk vertices) can be verified in polynomial time, the
Vertex Cover Problem is in NP.
14 b)
i. Calculate the value of 2p+q
Given the Boolean formula ϕ=(x1∨¬x2∨x4)∧(¬x1∨x3∨¬x4)∧(x1∨x2∨¬x3)∧(¬x2∨x3∨¬x4)
Number of variables p: The formula has 4 variables: x1,x2,x3,x4x Therefore, p=4.
Number of clauses q: The formula has 4 clauses, which are the individual disjunctions
connected by conjunctions. Therefore, q=4.
Now, we can compute 2p+q = 2 x 4 +4 = 12 :
ii. Does the assignment x1=1,¬x2=1,x3=0,¬x4=0 satisfy the Boolean formula ϕ?
The assignment translates to:
 x1=1 x2=0 x3=0 x4=1
We substitute these values into each clause of ϕ to check whether the formula evaluates to
true (1).
1. Clause 1 is true.
2. Clause 2 is false.
3. Clause 3is true.
4. Clause 4 is true.
Since one clause (Clause 2) evaluates to false, the formula does not satisfy the given
assignment. Therefore, the assignment does not satisfy ϕ
iii. Find an assignment of x1,x2,x3,x4∈{0,1} that satisfies ϕ
Let's try the following assignment:
 x1=1 x2=1 x3=0 x4=0
Substitute these values into the clauses of ϕ:
 1. Clause 1 is true.
2. Clause 2 is true.
3. Clause 3: is true.
4. Clause 4: is true.
Since all the clauses evaluate to 1, this assignment satisfies the formula.
iv. When do you say a problem AAA is in class NP-hard?
A problem A is in class NP-hard if:
1. A is at least as hard as any problem in NP, meaning that every problem in NP can be
reduced to A in polynomial time.
2. It does not necessarily have to belong to NP; it could be outside NP, but it is at least
as difficult as the hardest problems in NP.
Answer: A problem A is NP-hard if every problem in NP can be reduced to it in polynomial
time.
v. Show that SAT is NP-complete
Since we assume SAT is NP-hard, we should just prove SAT is NP. This shows SAT is NP-
complete.
To show SAT is in NP:
Some assignment to some SAT formula will require substituting the values in the variable
and evaluating the boolean OR and AND. This required time of length of the formula which is
linear in the number of variables. Hence it is NP.