DAA MOCK TEST – 2
(All questions to be attempted)
Time: 2 hrs Max Marks: 100
SECTION – A (2 marks each)
Q1) Given a graph G=(V,E), where all edge weights are non-negative integers, the Bellman-
Ford algorithm and Dijkstra’s algorithm may produce different shortest-path trees even
though they always compute the same shortest-path weights. (True or False).Justify your
answer.
Q2) While inserting the elements 50, 30, 70, 40, 35, 65 in an empty binary search tree (BST)
in the sequence shown, the element in the lowest level is ________.
Q3) Given a Directed Acyclic Graph (DAG) with the following edges:
• X→Y
• X→Z
• Y→W
• Z→W
• W→V
Which of the following are valid topological orderings?
Q4) Which of the following pairs of algorithms and their associated design paradigms is/are
correctly matched?
A. Dijkstra’s algorithm – Greedy method
B. Merge Sort – Divide and Conquer
C. 0/1 Knapsack – Dynamic Programming
D. N-Queens Problem – Backtracking
• A and B only
• A, B, and C only
• All of the above
• B, C, and D only
Q5) Let G be a connected undirected graph with 80 vertices and 300 edges. The weight of a
minimum spanning tree (MST) of GGG is 2000. Now, suppose the weight of each edge in
the graph is decreased by 5. What will be the weight of the new minimum spanning tree?
SECTION – B (6 marks each)
Q1) At Code Craft School, students are given a programming assignment to demonstrate their
understanding of sorting algorithms.
• Rahul decides to solve the problem using Bubble Sort, carefully comparing and
swapping adjacent numbers until the list is sorted.
• Raj takes a more strategic approach with Selection Sort, identifying the smallest
unsorted number in each round and placing it in the correct position.
The list they are given is: [8, 4, 6, 2, 5]
Their instructor, curious to compare their approaches, asks:
• How many passes did Rahul make to sort the list completely using Bubble Sort?
• How many comparisons did Raj perform to finish sorting using Selection Sort?
Q2) Let A = "data science" and B = "statistical".
Let y be the length of the longest common subsequence (not necessarily contiguous)
between A and B,
and x be the number of such longest common subsequences.
Then, compute the value of: 2x+3y = ?
Q3) Let G=(V,E) be a connected, weighted graph.
Let T1 and T2 be two minimum spanning trees (MSTs) of G, and let β∈R
Then, the number of edges in T1 of weight β is the same as the number of edges in T2 of
weight β.Is this statement true or false?
Q4) Given a text array T [1...n] and a pattern array P [1...m] such that T and P are characters
taken from the alphabet Σ, where Σ= {a, b,c,...,z}. The string matching problem is to find
an occurrence of P in T. A pattern occurs with shift s in T if P [1...m] =T[s+1...s+m].
Consider the arrays:
A=0000100010010 and P=10001 Then find the sum of the value of all s is-------.
Q5) Solve the following recurrence relation using Master’s theorem-
T(n) = 6T(n/2) + n2
SECTION – C (12 marks each)
Q1) When do Dijkstra and the bellman ford algorithm both fail to find a shortest path? Can
Bellman Ford detect all negative weight cycles in a graph? Apply Bellman Ford algorithm
on the following table:
From To Weight
A B 4
A C 2
B C 5
B D 10
C D 3
D E 4
E B -10
Q2) You are given the Exact Cover by 3-Sets (X3C) problem:
Given a finite set X with |X| = 3q and a collection C of 3-element subsets of X does there
exist a sub collection C′ ⊆ C such that every element in X is contained in exactly one
member of C′?
Prove that X3C is NP-Complete.
Q3) Consider the weights and values of items listed below. Note that there is only one unit of
each item.
Number Weight (in Kgs) Value (in Rupees)
1 5 25
2 7 40
3 4 20
4 3 24
The task is to pick a subset of these items such that their total weight is not more than 10
and their total value is maximized. Moreover, no item may be split. The total value of items
picked by an optimal algorithm is V_opt. A greedy algorithm sorts the items by their
value/weight ratios in descending order and packs them greedily, starting from the first
item in the ordered list. The total value of items picked by the greedy algorithm is denoted
V_greedy. The value of (V_opt – V_greedy) =?
Q4) Consider the following characters along with their respective frequencies in a given
message
Character D E _ A T
Frequency 12 5 8 20 15
Using the Huffman coding algorithm, construct an optimal Huffman Tree.
Tasks:
a) Calculate the path length (depth in the tree) for each character
b) Find the total number of bits required to transmit the message “CU_COSC” using the
obtained Huffman Codes.
Q5) Consider a text
Text (T) : ababcababcac
Pattern (P) : ababc
Using KMP(Knuth – Morris Pratt) String matching algorithm.
a) Find the longest prefix that is also a suffix for the pattern P
b) Determine the number of comparisions required to find the occurrence of P in T.
c) Also determine the shift and index of the pattern.
