Algorithms — DPP Question Bank

(Merged)
Analysis of Algorithms, Design Strategies, Greedy Method, Dynamic Programming & Graph Algorithm, Heap
Algorithm & Backtracking/Branch-Bound — Questions Only

Analysis of Algorithms – DPP

[MCQ] 2.
Consider two function f(n) =10n+2logn and g(n) = 5n + 2(logn)^2, then which of the following is correct option?
(a) f(n) = θ(g(n)) (b) f(n) = O(g(n))
(c) f(n) = ω(g(n^2)) (d) None of the above

[MCQ] 3.
Consider two function f(n) = √n and g(n) = n logn + n then f(n)/g(n) is equivalent to how many of the following
given below? _______.
(i) o(n^-1/2) (ii) O(n^-1/2)
(iii) Ω(1/logn) (iv) θ(n^-1/2)

[MCQ] 4.
Consider the following C-code
void foo (int x)
{
int a = 1;
if (n == 1)
return;
for (; a ≤ n; a++)
{
printf("GATEWALLAH");
break;
}
}
What is the worst time complexity of above program?
(a) O(1) (b) O(n)
(c) O(log n) (d) O√n

[MCQ] 5.
Find the time complexity of the following summation, assume that k is constant, k > 0
Σ(x=1 to n) Σ(y=x+1 to n) 1/k
(a) O(n^2) (b) O(n)
(c) O(n^3) (d) None of the above

[NAT] 6.
How many of the following expressions correctly describes T(n) = nlog(n^2)? ______
(a) θ(n^2) (b) O(n)
(c) Ω(n) (d) O(n^2)

[MCQ] 7.
Consider two function f1(n) = n^(2^n) and f2(n) = n^(n^2) then which of the following is true.
(a) f1(n) = O(f2(n)) (b) f1(n) = θ(f2(n))
(c) f1(n) = ω(f2(n)) (d) None of these
Design Strategies – DPP
[MCQ] 1.
Consider an array containing the following elements in unsorted order (placed randomly) but 120 as first elements
120 160 30 190 14 24 70 180 110
Quick sort partitioning algorithm is applied by choosing first elements as pivot element. Then what is the total
number of arrangements of array integers are possible preserving the effect of first pass of partitioning algorithm.
(a) 680 (b) 700
(c) 720 (d) 740

[MCQ] 2.
Let T(n) = [n(log(n^3) – logn) + logn]n + logn.
complexity of T(n) is
(a) O(n^2) (b) O(n^3)
(c) O(nlogn) (d) O(n^2 logn)

[MCQ] 3.
Assume that there are 4 sorted lists of n/4 elements each, if these lists are merged into a single sorted list of 'n'
elements then how many key comparisons are required in the worst case using an efficient algorithm?
(a) 2n – 3 (b) (7/4)n – 3
(c) (9/4)n – 3 (d) (6/4)n – 3

[NAT] 4.
Consider the number in the sequence
2 5 11 17 19 21 26 33 39 40 51 65 79 88 99
Using binary search, the number of comparisons required to search elements '2' is____

[MCQ] 5.
Merging 4 sorted files having 400, 100, 250, 50 records will take O (___) time?
(a) 800 (b) 400
(c) 200 (d) 100

[NAT] 6.
Consider a machine which needs a minimum of 50 seconds to sort 500 names by quick sort, then what is the
minimum time required to sort 50 names (approximately)is _____ (round off to 2 decimal)

[NAT] 7.
What is the total number of comparisons that will be required in worst case to merge the following sorted files into a
single sorted file into a single sorted file by merging together two files at a time____.
Files: F1 F2 F3 F4
Number of records: 40 42 44 46
Greedy Method – DPP
[MCQ] 1.
Consider the following statements.
S1: Given a weighted declared graph with the distinct weights, the shortest path among any two vertices will be
unique.
S2: A minimum spanning tree can contain negative edges.
Choose the correct statements.
(a) Only S1 is true
(b) Only S2 is true
(c) Both S1 and S2 are true
(d) neither S1 nor S2 is true

[MCQ] 2.
Which of the statement is/are correct?
(a) First edge added by Kruskal's algorithm can be the last edge added by prim's algorithm
(b) In a graph, if one raises the length of all edge to the power of 3, the minimum spanning tree will stay the same.
(c) The heaviest edge in a graph cannot belong to the minimum spanning tree.
(d) The maximum spanning tree (spanning tree of maximum cost) can be computed by negating the cost of all the
edges in the graph and then computing minimum spanning tree.

[NAT] 3.
Consider the following instantons of the job for-scheduling problem with deadlines (Note: every Job takes one unit
time)
Job: J1 J2 J3 J4 J5 J6 J7
Deadline: 1 3 4 3 2 1 2
Profit: 3 5 20 18 1 6 30
What is the maximum profit generated by greedy algorithm ______?

[NAT] 4.
Consider is the weighted graph G given by (a graph on 4 vertices with edges: 2, 3, 3, 3, 3, 4 as weights forming a
complete-ish graph with two triangles sharing edges).
How many MST does G Have?

[MCQ] 5.
Let's suppose, we want to merge some sorted files where the number of records in each file is given below.
(15, 18, 20, 21, 24, 28, 30, 32, 35, 40, 45, 50) then what is the minimum number of comparisons required to merge
the following files?
(a) 1200 (b) 1225
(c) 1251 (d) 1255

[MCQ] 6.
Greedy algorithm fails to give an optimal solution to which of the following problems?
(p) Travelling salesman problem
(q) Job scheduling with deadlines and penalty
(r) Shortest path algorithm
(s) optimal merge pattern
(t) Huffman encoding
(a) p, q, r (b) r, s, t
(c) p, q, r, s, t (d) All of the above
'Dynamic Programming' & 'Graph Algorithm' – DPP
[MCQ] 1.
What is the time complexity of dynamic programming for matrix chain multiplication problem?
(a) O(n^2)
(b) O(n^3)
(c) O(nlogn)
(d) None of these

[NAT] 2.
Consider the matrices x, y and z with dimension 10 × 20, 20 × 30 respectively. Then what is the minimum number
of multiplications required to multiply the matrices? ________

[MCQ] 3.
What is the length of the LCS for the pair of subsequences given below.
P = ATGACTATAA
Q = GACTAATA
(a) 5 (b) 6
(c) 7 (d) 8

[MCQ] 4.
Consider a connected weighted graph G = (V, E), where |V| = n, |E| = m, if all the edges have distinct positive
integer weights, then the maximum number of minimum weight spanning trees in the graph is ?
(a) n (b) m
(c) 1 (d) n^(n–2)

[MCQ] 5.
What is the weight of the minimum spanning tree for the graph shown below? (graph with vertices connected in a
zigzag: edges 1,2,1,2,3,1)
(a) 7 (b) 8
(c) 9 (d) 10

[MCQ] 6.
How many minimum spanning tree does this graph have? (graph P,Q,R,S,T,U with edges P-Q=1, Q-R=3, P-S=3, Q-
S=2, Q-T=3, Q-U=1, R-U=6, S-T=12, T-U=3, S-U=3)
(a) 2 (b) 3
(c) 4 (d) 5

[MCQ] 7.
Consider the following problem with knapsack capacity of 8
Items: I1 I2 I3 I4
Profits: 13 8 7 3
Weights: 1 5 3 4
Which of the following item is not selected in the optimal solution of 0/1, knapsack problem?
(a) I1 only (b) I2 only
(c) I3 only (d) I4 only

[MCQ] 8.
Consider the following statements
S1: for every weighted graph and any two vertices p and q, Bellman ford algorithm starting at p will always return a
shortest path to q.
S2: At the termination of Bellman ford algorithm even if graph has negative weight cycle, correct shortest path is
found for vertex for which shortest path is well-defined.
Which of the statement is correct?
(a) only S1
(b) only S2
(c) Both S1 and S2 are true
(d) neither S1 nor S2 is true
'Heap Algorithm' & 'Backtracking and Branch-Bound' – DPP
[MCQ] 1.
Consider the statements.
S1: Merge-sort, quick-sort and bubble sort are comparison-based sorting algorithms
S2: A reverse-sorted array (ie. ……decreasing order) is always max-heap
(a) Only S1 is true
(b) Only S2 is true
(c) Both S1 and S2 are true
(d) Neither S1 nor S2 is true.

[MCQ] 2.
Consider a binary search tree which is also a complete binary tree. The problem is to convert the BST which is given
into a minheap with the condition that, all the values in the left subtree of a node should be less than all the values in
the right subtree of the node. This condition is applied on all the nodes in the process of converting BST into
minheap.
Input: root 8, children 4 and 12; 4's children 2, 6; 12's children 10, 14.
Output: root 2, children 4 and 10; 4's children 6, 8; 10's children 12, 14.
What will be the worst-case time complexity (tightest) of given problem, if we can take auxiliary space of O(n)?
(a) O(n) (b) O(n^2)
(c) O(logn) (d) O(nlogn)

[MCQ] 3.
How many different min-heap are possible with keys 1 2 3 4 5?
(a) 5 (b) 6
(c) 7 (d) 8

[MCQ] 4.
What is the maximum number of exchanges required to order an array of 5 elements using the selection sort? ____
(a) 1 (b) 2
(c) 3 (d) 4

[NAT] 5.
Number of undirected graph (not necessarily connected) can be constructed by given set V = [1, 2, 3, 4] of 4 vertices
are ____.

[NAT] 6.
The number of spanning trees of an undirected completed graph with 7 nodes is _____

[MCQ] 7.
consider the following statements
S1: Backtracking is an algorithm technique for solving problems reclusively by trying to build a solution
incrementally.
S2: Time complexity of N-Queens algorithm is O(n!)
Which statement is true?
(a) only S1
(b) only S2
(c) Both S1 and S2 are true
(d) Neither S1 nor S2 is true