NATIONAL INSTITUTE OF TECHNOLOGY
KURUKSHETRA
Mid Term Examination I: Sept'2024 MM: 20)
Subject: Design Analysis of Aigorithms [CSPC2|) Duration: 50 mins
NOTE: 1. Thequestion puper contains TEN qestions.
2. Al questions are compulsory and huve equal weightage i.e. 2Marks each.
3. Assuwne suitable data, if missing.
4. Clearly state/specif" your answer in your solution'explanation.
Q1. Let T(n) be the number of different binary search trees on ndistinct elements and
T(n) = =1{T(k -1)T()}. then find the value of x.
Q2. Let T be a binary search tree with 15 nodes. Find the minimum and maximum possible
heights of this BST. (Assume that the height of atree with asingle node is zero)
Q3. Consider the following statements about an almostcomplete binary tree (with respect
to its structure)
S1: There is only asingle almost complete binary tree withnnodes.
S2: There are two distinct almost complete binary trees with n leaves.
Choose any one correct option from the following.
(i) Both are true (ii) Both are false (iii) S1 is true. S2 is false (iv) SI is false, S2 is true
Q4. Consider a hash table with 9 slots. The [Link] function is h(k) = k mod 9. The collisions are
resolved by chaining. The following keys are inserted in the order: 5, 28, 19, i5, 20, 33, 12,
17, 10. Find the average chain length in the hash table.
Q5. Consider the equality o Xard the following choices for X:
a) O(n) (b) O(n) (c) O(n') (d) n)
Then, in order to remain the above equation to be correct which choice(s) of X can be taken?
Explain briefly.
Q6. Consider the following asymptotically positive functions f(n), g(n), and h(n) such that
f(n) = O(g(n)), g(n) # O(f(n),g(n) = O(h(n)), and h(n) = O(g(n). Then, find the truth value
(True/False) of the following statements (provide an explanation for your answer)
a) f(n) t g(n) =O(h(n) + h(n)
b) f(n) = O(h(n))
c) h(n) # O(f(n))
d) f(n)h(n) O(g(n)h(n))
Q7. Consider sorting the following array of integers in ascending order using an inplace
Quicksort algorithm that uses the last element as the pivot. <60, 70, 80, 90, 100>.
Find the minimum number of swaps performed during this Quicksort.
Q8. Indicate, for each pair of expressions (A, B) in the table below whether A is O, o, 2, 0,
or of B. Assume that k> land c> lare constants. Write your answer in the form of the table
with "yes or "no" written in each box.
A
nk
n'gc c&n
09. The 2" vertices of a graph G corresponds to allsubsets of aset of size n, for n>6. Two
vertices of Gare adjacent if and only if the corresponding sets intersect in exactly two elements.
Find the number of vertices of degree zero in G.
Q10.
(i) Is it possible to have a graph (undirected) with the degree sequence:
(1, 3, 3, 3, 5, 6, 6)
(i) Is it possible to have a simple graph with the degree sequence:
(1, 1,3, 3, 3, 4, 6, 7)
NATONAL INSTEOE TEOL0GY
KORUKSETRA
Q. In udepth-first tversal ot' nundirevted guuplh Gwillh n veties, kedges ae matked us tree
cdyes. tindthe nunber of conneetedcomponents in the yupl1(;
Q2. A DES on adirected gruph with cight vertices (x, y. 1, w, », t, u, vË results in the following
discovery (d) nnd finishing () ime for cnch vertex. Then, lind the number ofdepth fist rees in
the resultunt depth-irst forest.
Discovery time (d) 4 7 14 12
Finishing time () ) I6
Q3. Considering the data given in Q2,what will he the truth value o the following statements
() The Graph cun contain aback cdge lronz i0x
(ii) TheGraph can contain a cross cdgc from s to w
Q4. In a Breadth-First Scarch (BFS), which of thc following depends onthe orderingof vertices
in cach adjacency list?
() thevaluc d/u/ assigned to a vertex u
(ii) the breadth-first trcc computed by thc BFS
(A) only() (B) only (ii) (C) both (i) &(i) (D) ncither (i) nor (ii) (E) can't say anythiny
Q5. Consider the following statements with respect to a brcadth-first search:
Sl:therc are no back edges and no forward edges for an undirected graph
S2: there are no forward edges for a direcied grapth
Whichof the following statemcnt(s) are true?
(A)only ST (B) only $2 (C) both SI &S2 (D) neither SInor S2 (E) can't say anything
Q6. LetG bc aconnccted undirected graph of 10 vertices and 30 cdyes. The weiyht of a minimurm
spanning tree of G is 50. When the weight of cach cdye of Gis inereased by three,then calculate
the change in the weight of a minimum spanning tree
Q7. Pri's algorithm is executed to find an MSTon the following undirected connected weighted
graph. Assume that Prim's algorithn is implcmented using a min-priority queue Q with key &n
attributes with usual meaning. What will be the content of O after three successive
extract-min
operations during the execution? (A ssume "5' as the starting vertex and whenever there is a choice
then the vertex with a low number is preferred)
3 8
08. What will be the cost of the minimum spanning tree (MST) of a graph with n nodes, which is
described as follows:
An undirected graph G(V, E)contains n (m > 2) nodes named v1,U2,.,Vn.
Two nodes v,v;
are connected if and only if 0 <|i-is2. Each edge (v,, v;) is assigneda weight i+j.
Hint: the answer must be in terms of n.
Q9. Insert the key value Q' into the followi.g ce of minimum degree3.
LGM,PX
|A B ( D E K NO RSTU v|Y Z
Q10. Find a topological sort of the graph depicted in the below figure. (process the vertices in
alphabetical order, whenever there is a choice)
F
NATIONAL INSTITUTE OF TECHNOLOGY, KURUKSHETRA
END SEM. THEORY EXAMINATION
Roll No...
Month and year: Dec.'2024 Total no. of pages used: 3
Program: [Link]. [Computer Engg.] Semester: 3rd
Subject: Design and Analysis of Algorithms Course code: CSPC-201
Maximum Marks: 50 Time allowed: 03 Hours
NOTE: . The question paper contains FOUR questions.
2. All Questions are compulsory.
3. Attempt all parts of aquestion together at one place.
4. Assume suitable data, if missing.
Q1. Attempt all parts of the following: [5+5+4=14]
(i) Using a Dynamic Programming (DP)-based bottom-up solution, construct a table to find out
allthe longest commonsubsequences (LCSs) of<qpqrr> and<pqprqrp>.
(ii)) Find an optimal parenthesization of a matrix chain product M1M2M3M4Ms whose sequence
of dimension is < 2, 25, 3, 16, 1, 1000 >, Also, calculate the minimum number of scalar
multiplications required to calculate the product by using a DP-based method in a bottom-up
fashion.
(ii) Show the results of insertingthe keys:
W, M, R, N, P
in order into the following B-tree with min degree 2.
H K L S
1|Pa ge
12
92. Attempt all parts of the following: [3+3+3+3 = 12]
(i) Show the dandIvalues that result from running the breadth-first search on the following
directed graph, using vertex 3 as the source.
2
G-2-4
3
4 2
5
6
(ii) For the graph given below, let a DFS be performed (assume that the DFS processes the
vertices in alphabetical order, whenever there is a choice). Calculate the discovery and finishing
times for each vertex, and show the classification of each edge.
(iii) Compute a minimumcost-spanning tree for the following graph using Prim'salgorithm.
Assume that the root vertex is a.
11
10
2
(iv) Find all the topologicalordering for the following directed graph:
2| Page
(3+3+3+3= 12]
03. Attempt all partsof the following:
have been marked
() A 5 × 5 chessboard is such that the middle row and middle column
inaccessible (i.e. you cannot place a queen at these places). Use a backtracking algorithm
to
place 4-Queens on this chessboard in a way that no queen attacks each other.
find the optimal solution
(ii) For the following given set of items and knapsack capacity of 60 kg,
for the fractional knapsack problem by using a greedy approach.
2 3 4
Item No
15 22 25
10
Weight 45 77 90
Value 30 40
frequencies by constructing a Huffman
(iii) Find an optimal Huffmancode for the following set of
A:3 B:2 C:6 D:8 E:2 F:6
tree:
with their start and finish times. Compute a
(iv) Consider the following ten activities along
schedule where the maximum number of activities can
take place.
A6 A7 A8 A9 A10
Al A2 A3 A4 A5
9 11 12
START1 2 3
11 13 12 14
FINISH 3 4 10
[3+3+3+3 = 12]
Q4. Attempt all parts of the following:
empty binary search tree in the given order:
(i))The following numbers are inserted into an
10, 1, 3, 5, 15, 12, 16
height is the maximum distance of a leaf node
What is the height of the binary search tree (the
from the root)?
recurrence
insertion sort and find the solution of this
(ii) Write a recurrence for recursive
relation.
an array. What is the content of the aray
(iii)Consider a binary max-heap implemented using
16, 13, 10, 8, 12}
after two delete (i.e. Extract-Max) operations on {25, 14,
hash function h(k) = k mod 9. Demonstrate what
(iv) Consider a hash table with 9 slots and the resolved by
happens upon inserting the keys 5, 28, 19, 15,
20, 33, 12, 17, and 10with collisions
chaining.
3| Page