Algorithms Test - 5 - PDF Flipbook

Algorithms Test - 5

289 Views
48 Downloads
PDF 4,582,031 Bytes

Download as PDF

REPORT DMCA


GATE
CSE

Algorithms

Test-05Solutions


ALGORITHMS
1. Assuming there are n keys and each key is in the range [0, m –

1]. The run time of bucket sort is
a) (n)
b) (n lg n)
c) (n lg m)
d) (n + m)
Answer: (d)
Solution:
Bucket sort is an algorithm that employees to sort n keys
assuming that each key is in the range [0, (m – 1)], then the run
time of buckets sort is O(n + m)
2. The cube root of a natural number n is defined as the largest
natural number m such that m3≤n. The complexity of computing
the cube root of n (n is represented in binary notation) is:
a) O(n) but not O(n0.5)
b) O(n0.5) but not O((log n)k) for any constant k > 0
c) O((1og n)k) for some constant k > 0, but not O((1og log n)m)

for any constant m > 0
d) O((1og log n)k) for some constant k > 0.5, but not O((log log

n)0.5)
Answer: (a)
Solution:
The number of comparisons will not be more than ‘n’.

1


3. The tightest lower bound on the number of comparisons, in the
worst case, for comparison-based sorting is of the order of
a) n
b) n2
c) n log n
d) n log2n
Answer: (c)
Solution:
The number of comparisons that a comparison sort algorithm
requires in proportion to n log n, where n is the number of
elements to sort.

4. ______is often used to prove the correctness of a recursive
function.
a) Diagonalization
b) Commutativity
c) Mathematical induction
d) Matrix Multiplication
Answer: (c)
Solution:
Correctness of recursive algorithms is often proved by
mathematical induction. This method consists of two parts: first,
you establish the basis, and then you use an inductive step

2


5. Suppose the elements 7, 2, 10 and 4 are inserted, in that order,
into the valid 3-ary max heap found in the above question, Q.17.
Which one of the following is the sequence of items in the array
representing the resultant heap?
a) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
b) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
c) 10, 9, 4, 5, 7, 6, 8, 2, 1, 3
d) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5
Answer: (a)
Solution:

3


6. An example of a dictionary-based coding technique is
a) run-length coding
b) Huffman coding
c) predictive coding
d) LZW coding
Answer: (d)
Solution:
Lempel-Ziv-Welch (LZW) is a universal lossless data
Comparision algorithm is the algorithm the widely used unit file
Comparision utility compress, and is used in the GIF image
format it’s an example for dictionary based Comparision
algorithm

7. Let W(n) and A(n) denote respectively, the worst case and
average case running time of an algorithm executed on an input
of size n. Which of the following is ALWAYS True?
a) A(n) = Ω(W(n))
b) A(n) = Θ(W(n))
c) A(n) = O (W(n))
d) A(n) = o(W(n))
Answer: (c)
Solution:
Average case running time always less than (or) equal to worst
case Time
∴ A(n): O(w(n))
By definition of asymptotic notations

4


Average lies always between the best and the worst case
inclusive.
8. Which traversal techniques list the nodes of a binary search tree
ascending order?
a) post-order
b) in-order
c) pre-order
d) linear-order
Answer: (b)
Solution:
Inorder traversal of binary search tree gives always sorted order
9. Given a f low graph with 10 nodes, 13 edges and one connected
components, the number of regions and the number of predicate
(decision) nodes in the flow graph will be
a) 4, 5
b) 5, 4
c) 5, 1
d) 13, 8
Answer: (b)
Solution:
Since, cyclomatic complexity (CC) from the graph is
CC = Number of predicate node (p) +1
CC = e – n + 2k, where e number of edges
n number of vertices and k number of connected component
CC = number of regions

5


⟹ p + 1 = e – n + 2k
⟹ p + 1 = 13 – 10 + 2 × 1
⟹p+1=5
⟹p=4
And number of regions = 5
10. Given below are some algorithms, and some algorithm design
paradigms.
List-I
1. Dijkstra’s shortest path
2. Floyd-warshall algorithm to compute all pairs shortest path
3. Binary search on a shortest array
4. Backtracking search on a graph
List-II
i. Divide and conquer
ii. Dynamic programming
iii. Greedy design
iv. Depth –first –search
v. Breadth-first search
Match the above algorithms on the left to the corresponding
design paradigm they follow.
a) 1 ‒ i, 2 ‒ iii, 3 ‒ i, 4 ‒ v
b) 1‒ iii, 2 ‒ ii, 3 ‒ i, 4 ‒ v
c) 1‒ iii, 2 ‒ ii, 3 ‒ i, 4 ‒ iv
d) 1‒ iii, 2 ‒ ii, 3 ‒ i, 4 ‒ v
Answer: (c)

6


11. The following Linear Programming problem has :
Max
Z = x1 + x2
x1 – x2 ≥ 0
3x1 – x2 ≤ -3
X1. X2 ≥ 0
And

a) Feasible solution
b) No feasible solution
c) Unbounded solution
d) Single Point as solution
Answer: (b)
Solution:
If the primal problem is feasible, but unboundead in the
direction of optimization, then the dual hasno feasible solution
otherwise, if the primal problem has an optimal solution, then
the dual has also an optimal solution
12. Let G(V, E) be an undirected graph with positive edge weights.
Dijkstra's single source shortest path algorithm can be
implemented using the binary heap data structure with time
complexity:
a) O(|V2|)
b) O(|E| + |V| log |V|)
c) O(|V| log| V|)
d) O((|E| + |V|)log|V|)

7


Answer: (b)
Solution:
Using Binary heap Data structure we time complexity O((|E| +
|V| )1og |V|)
13. An example of a non-adaptive routing algorithm is:

a) Shortest path routing
b) Centralized routing
c) Baran's hot potato algorithm
d) Baran's backward learning algorithm
Answer: (a)
Solution:
Adaptive routing algorithm rotes change dynamically as
function of current state of network
Non-Adaptive routing algorithm rotes are computed in
advance off-line and download to router when booted these are
static and fixed
Non-Adaptive routing algorithm rotes are shortest paths
routing and flooding
Adaptive routing algorithm are distance vector routing and link
state routing algorithm.

8


14. 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: (c)

Solution:

In-order traversal when carried out on Binary Search Tree,

results in a sorted list.

15. ln a complete binary tree of n nodes, how far are the two most

distant nodes? Assume each edge in the path counts as!

a) About log2 n

b) About 2 log2 n

c) About n log2 n

d) About2n

Answer: (b)

Solution:

In a complete binary tree two most distant node can be the leaf

nodes on each end = log( ) + log( ) = 2log( ).
22 2

9


16. An element of an array X is called a leader if it is greater than
all Elene 4th to the right of it in X. The best algorithm to find all
leaders in an array
a) Solves it using divide and conquer in time Θ(n log n)
b) Solves it in linear time using a left to right pass of the array
c) Solves it in linear time using a right to left pass of the array
d) Solves it in time Θ(n2)
Answer: (b)
Solution:
Algorithm to determine leaders in an array:
int max = a[n]
for i ← n – 1 to by -1
{
if{a[i] > ma)
{
print a[i];
max = a[i]
}
}
While scanning the array from right to left remember the
greatest element seen so far and compare it with the current
element to test for leadership.

10


17. in a weighted code with weight 6, 4, 2, ‒3 the decimal 5 is

represented by:

a) 0101

b) 0111

c) 1011

d) 1000

Answer: (c)

Solution:

in a weighted code 6, 4, 2, ‒3, the decimal 5 can be represented

by = 6 + 0 + 2 + (‒3) = 8 – 3 = 5

means 1011

18. Given the problem to maximize f(x), X = (x1, x2, …xn) subject

to m number of inequality constraints.gi (x) ≤ bi, i = 1, 2, …m

including the non-negativity constraints x ≥ 0.Which of the

following conditions is a Kuhn-Tucker necessary condition for a

local maxima at x?

a) ( ̅ � ̅) = 0, j = 1, 2…m


b) � [gi( � ) ‒ bi] = 0, 1 = 1, 2…m

c) gi( � ) ≤ bi, I = 1, 2..m

d) all of the above

Answer: (d)

Solution:

kuhh-Tucker necessary conditions:the necessary conditions for a

local maxima or stationary points(s) at ̅ are:

11


(i) ( ̅, ̅, � ) = 0, j = 1, 2,…n


(ii) ̅ [ ( ̅) ‒ ] = 0

(iii) ( ̅) ≤
(iv) ̅ ≥ 0, I = 1, 2,..,m

19. Converting a primitive type data into its corresponding

wrapper class object instance is called

a) Boxing

b) Wrapping

c) instantiation

d) Auto boxing

Answer: (d)

Solution:

Auto boxing is the automatic conversion that the java compiler

makes between the primitive types and their corresponding

object wrapper classes for example, converting an ‘int’ to an

‘integer’, a ‘Double’ to a ‘double’ and so on, if the conversion

goes the other way, this is called unboxing

20. To determine the efficiency of an algorithm the time factor is

measured by:

a) Counting micro seconds

b) Counting number of key operations

c) Counting number of statements

d) Counting kilobytes of algorithm

Answer: (b)

12


Solution:
Time complexity is commonly estimated by counting the
number of elementary operations performed by the algorithms
where an elementary thus the amount of time taken and the
number of elementary operations performed by the algorithm
differ by at most a constant factor
21. Let s be a sorted array of n integers. Let t(n) denote the time
taken for the most efficient algorithm to determine if there are
two elements with sum less than 1000 in s. Which of the
following statements is true?
a) t(n) is O(1)
b) n ≤ t(n) ≤ n 2
c) n 2 ≤ t(n) < (2n)
d) t(n) = (2n)
Answer: (a)
22. Given following graphs:

Which of the following is correct?
a) G, contains Euler circuit and G, does not contain Euler

circuit.
b) Gr does not contain Euler circuit and G, contains Euler

circuit.

13


c) Both G, and G, do not contain Euler circuit.
d) Both G, and G, contain Euler circuit.
Answer: (c)
Solution:
An Euler path is a path that uses every edge of a graph exactly
once, An Euler circuit is a circuit that uses every edge of a
graph exactly once a simple connected graph has Euler path
only if graph zero or two total number of odd degree sequences
and Euler circuit has only even degree
Therefore

23. Which one of the following binary search tree is optimal, if
probabilities of successful search and unsuccessful search are
same?
a)

14


b)

c)

d)
Answer: (d)
Solution:
Given binary tree is balance binary tree so, it gives optimal

15


24. Match the algorithms with their time complexities

Algorithm Time complexity
(P) Towers of Hanoi with n disks (i) ( 2)

(Q) Binary search given n sorted (ii) (n logn)

Numbers (iii) (2 )
(R) Heap sort given n numbers

At the worst case

(S) Addition of two n×n matrices (iv) (log n)

a) P → (iii), Q → (iv), R → (i), S → (ii)

b) P → (iv), Q → (iii), R→ (i), S → (ii)

c) P → (iii), Q → (iv), R→ (ii), S → (i)

d) P → (iv), Q → (iii), R→ (ii), S → (i)

Answer: (c)

Solution:

P → (iii)

Q → (iv)

R→ (ii)

S → (i)

25. Let A and I be two n x n matrices. The efficient algorithm to

multiply the two matrices has the time complexity

a) O(n3)

b) O (n2.81)

c) O (n2.67)

d) O (n2)

Answer: (b)

16


Solution:

using dynamic programming there exist algorithms that achieve

better complexity than the native O(n3) solving Strassen

algorithms achieves a complexity of O(n2.807) by reducing the

number of multiplications required for each 2×2 sub- matrix

the fastest known matrix multiplication algorithm is coppersmith

–win grad algorithm with a complexity of O(n2.3737).

26. The minimum number of nodes in a binary tree of depth d(root

is at level 0) is

a) 2dd ‒1

b) 2d+1 ‒ 1

c) d + 1

d) d

Answer: (b)

Solution

in a binary tree you have 1 root, 2 sons of that root 4 grandsons,

8 grand- grandsons, and so on so the total number of nodes is

the sum of the geometric series

1 + 2 + 4 + 8+..+2d = 2 +1−1
2−1

= 2 +1 − 1

where d is the depth (i.e., for d = 0, we have 1 node)

17


27. The usual Θ (n2) implementation of insertion Sort to sort an
array uses linear search to identify the position where an
element is to be inserted into the already sorted part of the array.
If instead, we use binary search to identify the position, the
worst case running time will
a) remain Θ (n2)
b) become Θ (n (log n)2)
c) become Θ (n log n)
d) become Θ (n)
Answer: (c)
Solution:
Binary search takes time of O(1og n) for a set of n-elements.
Total time for n-elements = O(n log n)

28. Given a binary tree who’s in order and preorder' traversal are
given by
in order: EICFBGDJHK
Preorder: BCEIFDGHJK
The post order traversal of the above binary tree is
a) IEFCGJKHDB
b) IEFCJGKHDB
c) IEFCGJHDB
d) IEFCGJKDBH
Answer: (a)
Solution:
in order: EICFBGDJHK

18


Preorder: BCEIFDGHJK
Construction of binary tree using inorder and preorder:

29. The power dissipation of a flip-flop is 3 mW. The power
dissipation of a digital system with 4 flip-flops is given by
a) 34 mW
b) 43 mW
c) 4/3 mW
d) 12mW
Answer: (d)
Solution:
Given power dissipation of one flip flop is 3 mW so, power
dissipation of 4 flip-flop = 4 × 3 = 12mW

30. in a B tree of order 5, the following keys are inserted as (c)
follows: 7, 8, 1, 4, 13, 20, 2, 6 and 5
How many elements are present in the root of the tree?
a) 1
b) 2
c) 5
d) 4
Answer: (b)

19


Solution:
Given order of B-tree is 5, therefore

20


Data Loading...