Algorithms Test - 1 - PDF Flipbook
Algorithms Test - 1
301 Views
30 Downloads
PDF 4,732,435 Bytes
GATE
CSE
Algorithms
Test-01Solutions
ALGORITHMS
1. The running time of the following algorithm Procedure A(n) If
n < = 2 return (1) else return (A (┌ √ ┐));Is best described by
a) O (n).
b) O (log n).
c) O (log log n).
d) O (1).
Answer: (c)
Solution:
T(n) = 1, n ≤ 2
T(n) = T� √ � + K, n > 2
N2-k = 2
2-k = logn2
2k = log2 n ⟹ k = log log2 n
2. A machine needs a minimum of 100 sec to sort 1000 names by
quick sort. The minimum time needed to sort 100 names will
be approximately
a) 50.2 sec
b) 6.7 sec
c) 72.7 sec
d) 11.2 sec
Answer: (b)
Solution:
Running time of quick sort = n log2 n
Hence, n = 1000
1
100sec = c × 1000 × log 1000
C = 0.01
For 100names,
Time = 0.01 × 100 × log 100 = 6.7 sec
3. Consider the following three claims
I. (n+ K)m = (nm). Where k and m are constants
II. 2n+1 = O(2n)
III. 22n = O(2n)
Which of these claims are correct?
a) I and II
b) I and III
c) II and III
d) I, II, and III
Answer: (a)
Solution:
i. (n + k)m is polynomial of power m
∴ O(nm) is true
ii. 2n+1 = O(2n.2) = O(2n)
∴ it is true
iii. 22n = O(2n.2)
≠ O(2n)
∴ I and II only are correct
2
4. What will be the cost of the minimum spanning tree (MST) of
such a graph with n nodes?
a) 1 (11 2 − 5 )
12
b) n2 – n + 1
c) 6n – 11
d) 2n + 1
Answer: (b)
Solution:
We observe a pattern in weight of MST being formed:
For n = 3 ⟹ (1+ 2 + 3) + (1)
For n = 4 ⟹ (1 + 2 + 3 + 4) + (1 + 2)
For n = 5 ⟹ (1 + 2 + 3 + 4 + 5) + (1 + 2 + 3)
For n = 3 ⟹ (1 + 2 + 3 + 4 + 5 + 6) + (1+ 2 + 3 + 4)
In general, total weight of MST for n;
= ∑ni=1 i + ∑in=−12 n2 − n + 1
5. An example of a data mining algorithm which uses squared
error score function is:
a) CART algorithm
b) back propagation algorithm
c) a priori algorithm
d) vector space algorithm
Answers: (b)
Solution:
Back propagation algorithm uses square error score function,
while CART algorithm uses cross validates and loss function,
3
and A priority algorithm uses support/actually as a square as a
sequencer error score function.
6. What is the content of the array after two delete operations on
the correct answer to the previous question?
a) {14, 13, 12, 10, 8}
b) {14, 12, 13, 8, 10}
c) {14, 13, 8, 12, 10}
d) {14, 13, 12, 8, 10}
Answer: (d)
Solution:
25
14 16
14 16 8 12
After deleting (25)
16 After deleting (16) 25
16
14 12 13
14 12 8 10 8
The height of a Max Heap is Θ (log n). While insertion, we need
to traverse from leaf element to root (in worst). If we perform
binary search for finding the correct position then we need to do
Θ (log log n) comparisons. In reality, it is not possible to
perform binary search on elements from leaf to root as they are
not in sequence.
4
7. G = (V, E) is an undirected simple graph in which each edge
has a distinct weight, and e is a particular edge of G. Which of
the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every
MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every
MST of G excludes e
a) I Only
b) II Only
c) both I and II
d) neither I nor II
Answer: (b)
Solution:
A1 B
4 32
C5 D
1. In the above diagram ‘3’ is lightest edge of cycle ADC but
MST of above graph do not contain that lightest(1) False.
∴Statement (1) False
2. Since ‘e’ is heaviest edge of some cycle. So it is not a cut edge
(or) bridge of the graph. So MST of G excludes e.
5
8. Given two sorted list of size 'm' and 'n’ respectively. The
number of comparison needed in the worst case by the merge
sort algorithm will be
a) mx n
b) max (m, n)
c) min (m, n)
d) m + n –1
Answer: (d)
Solution:
Minimum number of Comparision needed = O(m) or O(n)
{where all the elements in 1 list are smaller than the elements
in other list}
= maximum number of Comparision needed
= O (m + n – 1){when we are taking elements one-by-one from
each of the list}
9. Assume that the algorithms considered here sort the input
sequences in ascending order If the input is already in
ascending order, which of the following are TRUE?
i. Quick sort runs in Θ(n2) time
ii. Bubble sort runs in Θ(n2) time
iii. Merge sort runs in Θ(n) time
iv. Insertion sort runs in Θ(n) time
a) I and II only
b) I and III only
c) II and IV only
6
d) I and IV only
Answer: (d)
Solution:
If the input is already in ascending order then Quick sort takes
Θ (n) time,
Bubble sort takes Θ (n) time Merge sort takes Θ (n log n)
Insertion sort takes Θ(n) time.
10. The values of l(i, j) could be obtained by dynamic
programming based on the correct recursive definition of (ij)
of the form given above, using an array L[M,N], where M = m
+ l and N = n + 1, such that L[I, j] = l(i, j). Which one of the
following statements would be TRUE regarding the dynamic
programming solution for the recursive definition of l(i, j)?
a) All elements L should be initialized to 0 for the values of l(i,
j) to be properly computed.
b) The values of l(i, j) may be computed in a row major order
or column major order of L(M, N).
c) The values of l(i, j) cannot be computed in either row major
order or column major order of L(M, N).
d) L [p, q] needs to be computed before l[r, s] if either p < r or
q < s.
Answer: (b)
Solution:
L (i, j) values can be computed in a row major order or column
major order of L [M, N]
7
11. Consider the following sorting algorithms.
I. Quicksort
II. Heapsort
III. Merge sort
Which of them perform in least time in the worst case?
a) I and II only
b) II and III only
c) III only
d) I, II and III
Answer: (b)
Solution:
Worst case time complexity of Quick sort = O(n2) when input is
already sorted.
Worst case time complexity of Heap sort = O(n log n).
Worst case time complexity of merge sort = O(n logn)
12. Which one of the following array represents a binary max-
heap?
a) {25, 12, 16, 13, 10, 8, 14}
b) {25, 14, 13, 16, 10, 8, 12}
c) {25, 14, 16, 13, 10, 8, 12}
d) {25, 14, 12, 13, 10, 8, 16}
Answer: (c)
Solution:
In option (a) (13) cannot be the child of (12) in max-Heap.
In option (b) (16) cannot be the child of (14).
8
In option (d) (16) cannot be the child of smaller value node.
In A, s[3] which is the parent (13 >12).
In B, also a[3] > a[1](16 >14).
In D, a[6] which is right child of a[2] is greater than a[2](16
>12).
13. The average number of key comparisons done in a successful
sequential search in list of length n is:
a) log n
b) −1
2
c) n/2
d) +1
2
Answer: (d)
Solution:
If x is found at loc ‘1’
→1 Comparision
X is found at loc ‘2’
→2 Comparision
X is found at loc ‘3’
→n Comparision
Total Comparision = n (n + 1)/2
( +1)
Therefore average = 2
9
14. An algorithm is guaranteed to find an optimal solution if
a) h’ is always 0
b) g is always 1
c) h’ never overestimates h.
d) h’ never underestimates h.
Answer: (c)
Solution:
If the heuristic function h is admissible. Meaning that it never
over estimates the actual minimal cost of reaching the goal, then
A* is itself admissible-(or optimal) if a closed set is used. Then
h must also be monotonic (or consistent) for A* to be optimal
If we can guarantee that h’ never overestimates h. in that case
the A* algorithm is guaranteed to find an optimal path to goal, if
one exists.
15. The Breadth First Search algorithm has been implemented
using the queue data structure. One possible order of visiting
the nodes of the following graph is
a) MNOPQR
b) NQMPOR
c) QMNPRO
d) QMNPOR
Answer: (c)
Solution:
10
The remaining choices violates the FIFO discipline of the
queue and hence are not valid BFS traversals
16. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 are inserted in
that order into an initially empty binary search tree. The binary
search tree uses the usual ordering on natural numbers. What is
the in-order traversal sequence of the resultant tree?
a) 7 5 1 0 3 2 4 6 8 9
b) 0 2 4 3 1 6 5 9 8 7
c) 0 1 2 3 4 5 6 7 8 9
d) 9 8 6 4 2 3 0 1 5 7
Answer:(b)
Solution:
We know the in-order traversal of binary search tree is
increasing sorted order. i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
17. An example of an adaptive routing algorithm is:
a) distance vector routing
b) flooding
c) selective flooding
d) shortest path routing
Answer: (a)
Solution:
Adaptive routing is a routing algorithm that a router may select
a new route for each packet (even packets belonging ti the
same transmission) in response to change in condition and
topology of the networks.
11
A distance vector routing is a protocol in which routers inform
its neighbours of topology changes periodically.
18. Which of the following sorting algorithms has the lowest
worst-case complexity?
a) Merge sort
b) Bubble sort
c) Quick sort
d) Selection sort
Answer: (a)
Solution:
Merge sort takes a time of O(n log n) in all cases of input.
Here other sorting techniques have complexity of O (n2) in
worst case
19. Let G = (V, E) be a directed graph with n vertices. A path
from vi to vj in G is a sequence of vertices (vi, vi+1, ... , vj ) such
that (vk, vk+1) E for all k in i through j - 1. A simple path is a
path in which no vertex appears more than once.
Let A bean n × n array initialized as follows.
A[j, k] = �10 if (j, k) ∈ E
other wise
Consider the following algorithm.
For i = 1 to n
For j =1 to n
For k = 1 to n
A[j, k] = max(A[j, k], A[j, i] + A[I, k]);
12
Which of the following statements is necessarily true for all j
and k after termination of the above algorithm?
a) A[j, k] ≤ n
b) If A[j, j] ≥ n –1, then G has a Hamiltonian cycle
c) If there exists a path from j to k, A[j, k] contains the longest
path length from j to k
d) If there exists a path from j to k, every simple path from j to
k contains at most A [j, k] edges.
Answer: (c)
Solution:
It is just opposite of all pairs shortest path, where max
replaces min; therefore it finds longest path cost from j to k;
20. in delta rule for error minimization
a) weight are adjusted w.r.to change in the output
b) weight are adjusted w.r.to difference between desired output
and actual output
c) weight are adjusted w.r.to difference between input and
output
d) none of the above
Answer: (b)
Solution:
In Delta rule for error minimization, weights are adjusted with
respect to different between desired output and actual output.
13
21. For merging two sorted lists of sizes m and n into a sorted list
of size m + n, we require comparisons of
a) O(m)
b) O(n)
c) O(m + n)
d) O (log m + 1og n)
Answer: (c)
Solution:
The complexity depends on the number of comparisons
involved in the merging process, which is not more than (m +
n) we can use merge sort logic.
22. Consider the following graph:
Which one of the following is NOT the sequence of edges added
to the minimum spanning tree using Kruskal's algorithm?
a) (b, e) (e, f) (a, c) (b, c) (f, e) (c, d)
b) (b, e) (e, f) (a, c) (f, g) (b, c) (c, d)
c) (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)
d) (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)
Answer: (d)
Solution:
14
After adding (b, e) one can add either (e, f) or (a, c) Kruskals
algorithm works based on greedy strategy (picks minimum
weight edge). Weight of edge (a, c) is less than (b, c). So it
cannot come after (b, c).
23. Consider an undirected graph G where self-loops are not
allowed. The vertex set of G is {(i, j) |1≤ i ≤ 12, 1≤ j < 12}
there is an edge between (a, b) and (C, D) if |A– C| ≤ 1or |b –d|
≤ 1. The number of edges in this graph is
a) 726
b) 796
c) 506
d) 616
Answer: (c)
Solution:
Total number of vertices = 12*12=144
The graph formed by the description contains 4(corner)
vertices of degree 3 and 40(external) vertices of degree 5 and
100(remaining/internal) vertices of degree 8.
According to (Handshake thermos):
2|E| = sum of degrees
2|E| = 4 * 2 * + 40 * 5 + 100 * 8
2|E| = 1012
|E| = 1012 = 506 edges
2
15
24. N items are stored in a sorted doubly linked list. For a delete
operation, a pointer is provided to the record to be deleted. For
a decrease-key operation, a pointer is provided to the record on
which the operation is to be performed. An algorithm performs
the following operations on the list in this order: Θ (N) delete,
O (log N) insert, O(log N) find, and Θ (N) decrease-key. What
is the time complexity of all these operations put together?
a) Θ (log2 N)
b) Θ (N)
c) Θ (N2)
d) Θ (N2log N)
Answer: (c)
25. Consider the following recurrence:
T (n) = 2T (┌√ ┐) +1 T (1) = 1
Which one of the following is true?
a) T(n) = Θ(log log n)
b) T(n) = Θ(log n)
c) T(n) = Θ(√ )
d) T(n) = Θ(n)
Answer: (a)
Solution:
Applying master theorem, case-1 applies and hence it is Θ
(log log n)
(or)
T(n) = 2t(√ ) +1
16
T(1) = 1
By continuing, till Kth iteration, we get
⟹ 21 = 2
⟹ 2-k = logn2 ⟹ K= log log2n
26. Let R be the rectangular window against which the lines are to
be clipped using 2D Sutherland Cohen line clipping algorithm.
The rectangular window has lower left-hand corner at (- 5, 1)
and upper right-hand corner at (3, 7). Consider the following
three lines for clipping with the given end point coordinates:
Line AB: A (– 6, 2) and B (– 1, 8)
Line CD: C (– 1, 5) and D (4, 8)
Line EF: E (– 2, 3) and F (1, 2)
Which of the following line(s) is/are candidate for clipping?
a) AB
b) CD
c) EF
d) AB and CD
Answer: (d)
Solution:
since , EF is completely inside window, so it is trivally visible
and do not need clipping
17
27. Consider the DAG with V = {1, 2, 3, 4, 5, 6}, shown below.
Which of the following is NOT a topological ordering?
a) 1 2 3 4 5 6
b) 1 3 2 4 5 6
c) 1 3 2 4 6 5
d) 3 2 4 1 6 5
Answer: (d)
Solution:
Topological sort/ordering starts with that vertex which does
not have any precedence In the given graph, vertex '3' has a
precedence from vertex '1' and hence it is incorrect.
28. In the following C function, let n > = m.
int gcd (n, m)
{
if (n% m = = 0) return m;
N = n% m;
Return gcd (m, n);
}
How many recursive calls are made by this function?
a) Θ (log2 n)
b) Ω (n)
18
c) Θ (1og2 log2)
d) Θ(√ )
Answer: (c)
29. In a full binary tree of height k, there are internal nodes.
a) 2k-1
b) 2K-1
c) 2K
d) 2K +1
Answer: (a)
Solution:
In full binary tree of height k maximum number of internal
nodes can be: =1 + 2 + 4 + 8 +..+ 2(k-1)
(Since at height k levels of binary tree that can be 2k)
= 2 −1 = (2k – 1)
2−1
30. Merge sort uses
a) Divide and conquer strategy
b) Backtracking approach
c) Heuristic search
d) Greedy approach
Answer: (a)
Solution:
In merge sort algorithm, for every iteration, array is divided
into two equal parts. It uses divide and conquer
19
Data Loading...