Algorithms Test - 3 - PDF Flipbook

Algorithms Test - 3

367 Views
64 Downloads
PDF 4,992,600 Bytes

Download as PDF

REPORT DMCA


GATE
CSE

Algorithms

Test-03Solutions


ALGORITHMS
1. Amax-heap is a heap where the value of each parent is greater

than or equal to the value of its children. Which of the following
is a max heap?
a)

b)

c)

d)

Answer: (b)

1


Solution:
Trees in (c) and (d) violate the property of Max-Heap. Tree (a)
satisfies the property of Max-Heap, but it is not a complete
Binary Tree. Tree (b) is the correct answer. (a) is not a complete
binary tree. In (c) and (d), heap property is not satisfied between
5 and 8.
2. 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 log2 n
Answer: (c)
3. A list of n strings, each of length n, is sorted into lexicographic
order using the merge-sort algorithm. The worst case running
time of this computation is:
a) O (n log n)
b) O (n2 log n)
c) O (n2 + log n)
d) O (n2)
Answer: (b)
Solution:
In merge-sort algorithm numbers of splits are proportional to
height and in each level work done is n2
∴ Total Time Complexity O(n2 log n)

2


The Complexity of Merge Sort for n elements is O(n log n)
4. With reference to implementation of different association

mining algorithms, identify the correct statement:
a) The FP growth method was usually better than the best

implementation of a prior algorithm
b) A priori algorithm is usually better than CHARM
c) A priori algorithm is good when the support required is low
d) At very low support the number of frequent items becomes

less
Answer: (a)
Solution:
FP-growth is more efficient than Apriori in respect to long
patens in Apriori algorithm, it occupies large space due to more
candidates and hence execution time is more candidate and
hence execution time is more CHARM was also usually better
than Apriori in some cases, CHAR was better than FP- growth
method
5. An algorithm to find the length of the longest monotonically
increasing sequence of numbers in an array A[0: n – 1] is given
below.
Let Li denote the length of the longest monotonically increasing
sequence starting at index i in the array.
Initialize Ln-1 = 1
For all I such that 0 ≤ i ≤ n – 2

3


Li = �1 + Li+1 if A[i] < A[i + 1]
1, other wise

Finally the length of the longest monotonically increasing

sequence is Max (L0, L1, ...... ,Ln-1).

Which of the following statements is TRUE?

a) The algorithm uses dynamic programming paradigm

b) The algorithm has a linear complexity and uses branch and

bound paradigm

c) The algorithm has a non-linear polynomial complexity and

uses branch and bound paradigm

d) The algorithm uses divide and conquer paradigm.

Answer: (a)

Solution:

The algorithm uses dynamic programming paradigm.

6. Floyd-War shall algorithm utilizes to solve the all-pairs shortest

paths problem on a directed graph in ____time

a) Greedy algorithm Θ (V3)

b) Greedy algorithm Θ (V2 log n)

c) Dynamic programming Θ (V3)

d) Dynamic programming Θ (V2 log n)

Answer: (c)

Solution:

The floyd-warshall algoritham is an example of dynamic

programming it finds shortest paths in a weighted graph with

positive oe negitive edge weights (but with no negitive cycle)

4


The Floyd- warshelsll algoritham compares all possible paths
though the graph between each pair of vertices it is able to do
this with Θ(|V|3) comparissions in a graph Therfore the time
com[plexity of the algoritham is Θ(|V|3)
7. Which one of the following is a valid sequence of elements in an
array representing 3-ary max heap?
a) 1, 3, 5, 6, 8, 9
b) 9, 6, 3, 1, 9, 5
c) 9, 3, 6, 8, 5, 1
d) 9, 5, 6, 8, 3, 1
Answer: (d)
Solution;

5


8. Let G = (V, E) be an undirected graph with a sub graph G1 =

(V1, E1). Weights are assigned to edges of G as follows.

W (e) = �1 0 if e ∈ 1
other wise

A single-source shortest path algorithm is executed on the

weighted graph (V, E, w) with an arbitrary vertex v1 of V1 as the
source. Which of the following, can always be inferred from the

path costs computed?

a) The number of edges in the shortest paths from v1 to all
vertices of G

b) G1 is connected
c) V1 forms a clique in G
d) G1 is a tree

Answer: (a)

Solution:

Number of edges in the shortest paths can be determined as a

result of Dijkstra's single source shortest paths algorithm.

9. Give as good a big-O estimate as possible for the following

functions:

(n log n + n2) (n3 + 2) and
(n! + 2n) (n3 + log (n2 + 1))

a) O (n5 + 2n2) and O (n3 + n!)

b) O (n5) and O (n3 * 2n)

c) O (n5) and O (n3 * n!)
d) O (n5 + 2n2) and O (n3 *2n)

Answer:(c)

6


Solution:

Let f and g be two functions defined on some subset of the real

numbers one writes f(x) = O(g(x)) as x → 0, if and only if and

only if there is a positive constant m such that for all sufficiently

large value of x in other words

⟹ |f(x)| ≤ m|g(x)| ∀x ≥ 0
⟹ |f(x) = O(g(x))

⟹ log →∞ ( ) = 0
( )

10. The recurrence relation T(n) mt � 2 � + 2 is satisfied by

a) (n2)

b) (nlog2m)

c) (n2 log n)

d) (n log n)

Answer: (b)

Solution:

The recurrence relation T(n) = mT(n/2) + a, n2

On solving using masters thermo for m > 4

T(n) = Θ (nlogm)

Also for m < 4

T(n) = Θ(n2)

And for m = 4

T(n) = Θ(n2 .log n)

This question where marks to all due to typographical error

7


11. The worst case running time to search for an element in a
balanced binary search tree with n2" elements is
a) Θ (n log n)
b) Θ (n2n)
c) Θ (n)
d) Θ (log n)
Answer: (c)
Solution:
Log2 (n 2n) = log2 n + log2 (2n)
= log2 n + n = Θ (n)

12. Following algorithm (s) can be used to soft n integers in the
range [1.....n3] in O(n) time?
a) Heap sort
b) Quick sort
c) Merge sort
d) Radix sort
Answer: (d)
Solution:
If we subtract each number by 1 then we get the range [0, n3 –
1]. Considering all number as 3-digit base n: each digit ranges
from 0 to n3-1. Sort this using radix sort. This uses only three
calls to counting sort. Finally, add 1 to all the numbers. Since
there are 3 calls, the complexity is O(3n) ≈ O(n).

8


13. In the following graph discovery time stamp and finishing time
stamps of depth first search(DFS) are shown as x/y, where x is
discovery time stamp and y is finishing time stamp.

It shows which of the following depth first forest?
a) {a, b, el {c, d, f, g, h}
b) {a, b, e} {c, d, h} {f, g}
c) {a, b, e} {f, g} {c, d} {h}
d) {a, b, c, d} {e, f, g} {h}
Answer: (a)
Solution:
As given graph with visited nod by depth first order is

DFS visited nodes as:
C → g → f →h → g → d →c
Then b → e →a

Then forest is {a, b, e}, {c, d, f, g, h}

9


14. Runtime polymorphism can be achieved by:
a) Accessing virtual function through the pointer of the base
class
b) Accessing virtual function through the object
c) The derived class
d) None of these
Answer: (a)
Solution:
You need to provide a virtual members function in base class
and overide it in derived class the actual method type of the
object pointed by the base class pointer

15. Match the pairs in the following
List I
a. Heap construction
b. Constructing hash table with linear probing
c. AVL tree construction
d. Digital tree construction
List II
P. Ω(n log 10 n)
Q. O (n)
R. O (n2)
S. O (n log2 n)
a) a – q, b – r, c – s, d – p
b) a – q, b – r, c – p, d – s
c) a – q, b – p, c – s, d – q

10


d) a – p, b – r, c – s, d – q
Answer: (a)
16. A tree with n vertices is called graceful, if its vertices can be
labelled with integers 1, 2, …n such that the absolute value of
the difference of the labels of adjacent vertices are all different.
Which of the following trees are graceful?

a) S1 and S2
b) S2and S3
c) S1and S3
d) S1, S2 and S3
Answer: (d)
Solution:
Caterpillar tree is a tree in which all the vertices are within
distance 1 of central path

11


Absolute value of the difference of the labels of adjacent
vertices is all different as defeated graceful tree in question
Hence, all (S1), (S2), and (S3) are graceful
17. Consider the following segment of C-code:

Int j, n;
J = 1;
While (j< = n)
J = j*2;
The number of comparisons made in the execution of the loop
for any n > 0 is:
a) [log2 n] + 1
b) n
c) [log 2 n]
d) [log2 n] + 1
Answer: (d)
Solution:
Since ‘j’ increases in power of 2; i.e 2, 4, 8… in the loop 2k ≤ n
when 2k > n loop exits, so number of comparisons made in
execution of loop for any n > 0 is ⌊log2 ⌋ + 1
18. G1 and G2 rare two graphs as shown:

a) Both G1 and planer graph

12


b) Both G1 and G2 are not planer graphs
c) G1 is planar and G2 is not planner graph
d) G1 is not planer and G2 is planar graph
Answer: (d)
Solution:

In planner graph:
(i) e ≤ 2n – 4 , (ii) e ≤ 3n – 6 if ∆
G1: n = 6, e = 9
⟹ e ≤ 2n – 4
⟹9≤2×6–4
⟹ 9 ≤ 8 false
G2: n = 6, e = 11
⟹ 11 ≤ 2n – 4
⟹ 11 ≤ 12 true

Therefore, only G2 is planner graph
19. Randomized Quick sort is an extension of Quick sort where the

pivot is chosen randomly. What is the worst case complexity of
sorting n numbers using randomized Quick sort?
a) O (n)
b) O (n log n)
c) O (n2)
d) O (n!)

13


Answer: (b)
20. Match the following:

List-I
a) Huffman codes
b) Optimal polygontriangulation
c) Activity selection problem
d) Quicksort
List-II
1. O(n2)
2. Θ(n3)
3. O(n log n)
4. Θ(n)
Codes:

AB C D
a) 1 2 4 3
b) 1 4 2 3
c) 3 2 4 1
d) 3 4 2 1
Answer: (c)
Solution:
Huffman coding takes O(n log n) time Quick sort having O(n2)
time complexity in worst case but average case O(n log n)
Activity selection problem has Θ(n) time complexity using
greedy method.

14


Optimal polygon triangulation has Θ(n3)time complexity using

dynamic programming.

Therefore, (a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)

21. Which of the following is true about the z-buffer algorithm?

a) It is a depth sort algorithm

b) No limitation on total number of objects in the scene

c) Comparison of objects is done

d) z-buffer is initialized to background colour at start of

algorithm

Answer: (a)

Solution:

Z-buffer algorithm is a depth sort algorithm. This algorithm is

used for hidden surface elimination.

22. Consider the following functions from positive integers to real

numbers: 10, √n, n, log 2, n, 100
The CORRECT n

arrangement of the above functions in

increasing order of asymptotic complexity is:

a) log2, n, 1n00, 10, √n, n
b) 1n00, 10, log2, n, √n, n
c) 10, 1n00,√n, log2, n, n
d) 1n00, log2, n,10, √n, n

Answer: (b)

15


Solution:

As n →∞, 100 < 10 < log 2 n < √n < n
n

23. Consider a Hamiltonian Graph (G) with no loops and parallel

edges. Which of the following is true with respect to this Graph

(G)?

S1: deg (v) ≥ n/2 for each vertex of G

S2: |E(G)| ≥ 1/2(n – 1) (n – 2) + 2 edges

S3: deg (v) + deg (w) > n

For every v and w not connected by an edge

a) S1 and S2

b) S2 and S3

c) S1 and S3

d) S1, S2 and S3

Answer: (d)

Solution:

S1: Dirac Theorem: A simple graph with n vertices (n ≥ 3) is

Hamiltonian if every vertex has degree n/2 or greater

S2: maximum number of edges in non-Hamilton graph is |E(G)|

≤ �( − 1)� + 1
2

Therefore, minimum number of edges in Hamiltonian graph is

|E(G)| ≥ �( − 1)� + 2
2

|E(G)| ≥ ( −1)( −2) +2
2

16


S3: Ore’s Theorem for Hamiltonian graph states that deg(v) +
deg (w) ≥ n for every v and w not connected by an edge

Let f and g be two functions defined on some subset of the real

number one writes f(x) = O(g(x)) as x → 0, if and only if there

is a positive constant such that for all sufficiently large value of

x in other words

⟹ |f(x) ≤ m|g(x)| ∀ ≥ x0

⟹ f(x) = O(g(x))

⟹ log →∞ ( ) = 0
( )

24. Which of the following connected simple graph has exactly

one spanning tree?

a) Complete graph

b) Hamiltonian graph

c) Euler graph

d) None of the above

Answer:(d)

Solution:

A connected simple graph has unique spanning tree only if

graph edges have distic edge weights

25. Let P be a Quick sort program to sort numbers in ascending

order using the first element as the pivot. Let t1 and t2 be the
number of comparisons made by P for the inputs [1 2 3 4 5l and

[4 1 5 3 2] respectively. Which one of the following holds?

a) t1 = 5
b) t1 < t2

17


c) t1 > t2

d) t1 = t2

Answer: (c)

Solution:

Case (i): If the array elements are in the increasing order then

the quick sort takes number of comparisons are

1 = ( −1)
2

Case (ii): If the array elements are randomly distributed then

the quick sort takes number of comparison are
t2= 2(n + 1) (logne + 0.577) − 4n

∴ t1 > t2
26. Which of the following statement is false?

a) Every tree is a bipartite graph

b) A tree contains a cycle

c) A tree with n nodes contains (n -1) edges

d) A tree is connected graph

Answer: (a)

Solution:

A bipartite graph cannot have odd length cycle and tree is

minimal connected graph having n vertices and (n – 1) edges

so, a tree cannot have any cycle so, every tree is a bipartite

graph

So, every tree is bipartite graph

18


27. The algorithm that will efficiently sort an array that is nearly
sorted except for the interchange of some adjacent pairs of
numbers like: {1, 3, 2, 5, 4, 6) is
a) Quick sort
b) Merge sort
c) Bubble-sort
d) Selection sort
Answer: (b)
Solution:
Bubble sort with take O(n) time when array already sorted,
since given array is almost sorted so other sorting also given
O(n log n) as best case

28. if a code is f-error correcting, the minimum Hamming distance
is equal to:
a) 2t + 1
b) 2
c) 2t – 1
d) t – 1
Answer: (a)
Solution:
If two code words are hamming distance d part it will take done
bit errors to convert one into the other
To detect (but not correct) up to d errors per length n, you need
a coding scheme where code words are at least (d + 1) apart in

19


hamming distance then d errors cannot change into another legal
code, so, we know there been an error
To correct d errors need code words (2d+1) apart, then even
with d error, distring will be d way from original (d+1) away
from nearest legal code still closest to original can be restricted
29. The in order and pre order Traversal of binary Tree are
dbeafcg and abdecfg respectively. The post order Traversal
a) dbefacg
b) debtagc
c) dbefcga
d) debfgca
Answer: (d)
Solution:
Given,
Inorder: d b e a f c g
Preorder: a b d e c f g

Construction of tree using in order and pre order
Therefore, post order is: d e b f g c a
30. Match the pairs in the following:
List – I
a. Streen’s matrix multiplication algorithm
b.Kruskals minimum spanning tree algorithm

20


c. Biconnected component algorithm
d.Floyd’s shortest path algorithm
List – II
p. Greedy method
q. Dynamic programming
r. Divide and Conquer
s Depth first search
a) a – r, b – p, c – s, d – q
b) a – p b – r, c – s, d – q
c) a – q, b – p, c – s, d – r
d) a – r, b – p, c – q, d – s
Solution: (a)

21


Click to View FlipBook Version Previous Book Buku Program Hari Anugerah Cemerlang 2019 Next Book Hair Transplant Treatment

Data Loading...