Roll No.

COER University
MID TERM EXAMINATION, EVEN SEMESTER, SESSION: 2024-25

Time: 1 Hour Max Marks: 20

Program Name & Specialization : Semester:
Course Name: ………………… Course Code:……………

Note: All questions are compulsory. No student is allowed to leave the examination hall before the completion of the
time.

PART-A (Attempt All the Questions) MM CO BL

Q. No 1 Consider a state space where the start state is number 1. The successor function for the 1
state numbered n returns two states numbered n+1 and n+2. Assume that the states in
the unexpanded state list are expanded in the ascending order of numbers and the
previously expanded states are not added to the unexpanded state list. Which ONE of
the following statements about breadth-first search (BFS) and depth-first search (DFS)
is true, when reaching the goal state number 6?

A. BFS expands more states than DFS.

B. DFS expands more states than BFS.
C. Both BFS and DFS expand equal number of states.
D. Both BFS and DFS do not reach the goal state number 6.
Q. No 2 Data are pushed to (PUSH operation) and popped from (POP operation) a stack in the 1
following order: PUSH 3; TOP; PUSH 7; TOP; PUSH 6; PUSH 9; TOP; POP; POP;
TOP; where the PUSH, POP and TOP operations of stack behave as discussed in the
class. Write the values returned by TOP for the sequence of operations above.
Q. No 3 Let x is the cost of MST G (V, E) and y is the cost of MST G (V, E2), 1
where E2 means:
If w (u, v) ∈ E then w2 (u, v) ∈ E2 and w ∈ real numbers. (Consider w is the weight/cost)
Find relationship between x and y. Need justification also.
1) x>=y 2) x<=y 3) x=y 4) None of these
Q. No 4 Let G be a connected, weighted graph. Prove that, if all edge weights in G are 1
distinct, then G has exactly one MST.
Q. No 5 Consider an undirected graph with vertex set {A, B, C, D, E, F, G} and edge set {AB, 1
AC, AD, BD, BE, CD, DE, DF, EF, FG}. A Breadth-First Search (BFS) is performed
starting from A as the root node. Which of the following is a tree edge?

i) BD ii) AD iii) DE iv) CD v) None

PART-B (Attempt Any Three Questions) MM CO BL

Q. No 6 Consider the following characters along with their respective frequencies in a given 2
message:
Character X Y Z W V U
Frequency 5 7 10 12 15 20
Using the Huffman coding algorithm, construct an optimal Huffman tree, where the
two highest frequency nodes are merged first, placing the higher frequency node
on the left and the lower frequency node on the right. Additionally, assign 1 to the
left edge and 0 to the right edge.
Tasks:
1. Determine the Huffman code for each character based on the constructed
tree.
2. Calculate the path length (depth in the tree) for each character.
3. Find the total number of bits required to transmit the message "XYZ"
using the obtained Huffman codes.
Q. No 7 Given an arbitrary connected graph G=(V,E) with edge weights in R+ will the 2
minimum cost edge in G (assume there is only one such edge in G) always be present
 in every MST of G? If your answer is YES then give a short justification, if it is NO
then give a counterexample.
Q. No 8 The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Find the 2
postorder traversal of the tree? Also find the height of a tree known as the length of the
longest path from the root to any leaf.
Q. No 9 Solve the following recurrence relation using Master’s theorem- 2
T(n) = √2T(n/2) + logn
Q. No 10 A list of numbers 42, 8, 23, 56, 34, 15, 9, 67 is sorted in descending order using the 2
bubble sort algorithm. Let the number of swaps required be X. If the same list is sorted
using selection sort, the total number of comparisons made is Y. Determine the value
of X - Y.

PART-C (Attempt Any Three Questions) MM CO BL

Q. No 11 Given four keys (Section-A), (Section-B), (Section-C), and (Section-D) with 3
respective probabilities 1/5, 2/5, 1/10, and 2/10, construct an Optimal Binary Search
Tree (OBST) using the Dynamic Programming (DP) approach. The objective is to
minimize the expected search cost by selecting an optimal arrangement of the keys in
a binary search tree. The cost of a search tree depends on the frequency of searching
for each key, meaning keys with higher probabilities should be placed closer to the root.
Using DP, compute the minimum search cost by considering all possible root selections
for different subtrees and determining the optimal tree structure. Finally, construct and
describe the OBST that achieves the lowest search cost.
If we consider that X represents the optimal BST having lowest cost and Y represents
the total number of BST then find the value of X+Y=?
Q. No 12 Consider a knapsack problem where there are four items, each with a specific weight 3
and value. The details of the items are as follows: Item 1 has a weight of 8 kg and a
value of 50 rupees, Item 2 has a weight of 6 kg and a value of 30 rupees, Item 3 has
a weight of 3 kg and a value of 18 rupees, and Item 4 has a weight of 4 kg and a value
of 25 rupees. The goal is to select a subset of these items such that the total weight does
not exceed 10 kg, while maximizing the total value. Each item can either be fully
included or excluded, but it cannot be divided. The selection is made using a greedy
approach, where items are chosen based on their value-to-weight ratio in descending
order, packing them greedily until the weight limit is reached. The total value obtained
using this greedy strategy is denoted as V_greedy. The difference between the optimal
value obtained using dynamic programming (V_opt) and the greedy approach
(V_greedy) needs to be determined.
Q. No 13 Consider two groups of students: CSE students and AI-ML students. A CSE student 3
was given a problem to compute B₁ × B₂ × B₃, where the matrices have dimensions 5
× 50, 50 × 4, and 4 × 10, respectively. The CSE student follows a greedy algorithm
(multiplying matrices that result in the least number of multiplications at each step) and
solves B₁ × B₂ × B₃ with N₁ multiplications. On the other hand, an AI-ML student
solved the same problem using a dynamic programming algorithm and required only
N₂ multiplications. How many multiplications were saved by the AI-ML student
compared to the CSE student?
Q. No 14 Consider two strings X = "abraca" and Y = "bacara". Let p be the length of the 3
longest common subsequence (LCS) between X and Y, and let q be the number of
such longest common subsequences. Compute the value of p + 10q.
Q. No 15 Consider a variation of the QuickSort algorithm where instead of selecting a single 3
pivot, two pivots are chosen to partition the array into three segments: elements smaller
than the first pivot, elements between the two pivots, and elements greater than the
second pivot. The three segments are then recursively sorted using the same approach.
Tasks:
i. Outline the modified DUAL-PIVOT-QUICKSORT (A, low, high) procedure,
where A is an array and low and high are indices into the array. Clearly describe how
the two pivots are chosen and how the partitioning process is performed.
ii. Provide a conjecture about the time complexity of this modified algorithm compared
to the standard QuickSort. Is it better, worse, or the same? Justify your answer with
reasoning.