Discrete Mathematics

Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The worst case occurs in quick sort when _________
Pivot is the median of the array
Pivot is the smallest element
Pivot is the middle element
None of the mentioned
Explanation:
This happens when the pivot is the smallest (or the largest) element. Then one of the partitions is empty, and we repeat recursively the procedure for N-1 elements.
Question 2
Marks : +2 | -2
Pass Ratio : 100%
If the entire list is searched sequentially without locating x in linear search, the solution is __________
0
-1
1
2
Explanation:
If the element is not found in the entire list, then the solution is 0.
Question 3
Marks : +2 | -2
Pass Ratio : 100%
The quotient and remainder when 18 is divided by 5 is?
2 and 3
1 and 2
3 and 2
3 and 3
Explanation:
According to the Division Algorithm 18 = 5(3) + 3. Hence, quotient when 18 divided by 5 is 3 = 18 div 5 and remainder when 18 divided by 5 is 3 = 18 mod 5.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
If a|b and a|c, then?
a|bc
c|a
a|(b+c)
b|a
Explanation:
If a|b and a|c then b = am and c = an for some integer m and n. Hence, b + c = a(m + n). Therefore, a|(b+c).
Question 5
Marks : +2 | -2
Pass Ratio : 100%
__________ comparisons required to sort the list 1, 2, 3…….n using insertion sort.
(n2 + n + 2) / 2
(n3 + n – 2) / 2
(n2 + n – 2) / 2
(n2 – n – 2) / 2
Explanation:
2+3+4+….6n = (n2 + n – 2) / 2.
Question 6
Marks : +2 | -2
Pass Ratio : 100%
The Worst case occur in linear search algorithm when _________
Item is somewhere in the middle of the array
Item is not in the array at all
Item is the last element in the array
Item is the last element in the array or is not there at all
Explanation:
The Worst case occur in linear search algorithm when Item is the last element in the array or is not there at all.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
The value of 155 mod 9 is?
0
1
2
3
Explanation:
By the Division algorithm 155 = 9(17) + 2. Where remainder is 155 mod 9.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
In ________ search each element is compared with x till not found.
Binary
Sequential
Merge
None of the mentioned
Explanation:
In linear or sequential search entire list is searched sequentially for x.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
The complexity of Fibonacci series is _________
O(2n)
O(log n)
O(n2)
O(n log n)
Explanation:
Fibonacci is f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1. Let g(n) = 2n. Now prove inductively that f(n) > = g(n).
Question 10
Marks : +2 | -2
Pass Ratio : 100%
An algorithm is a _________ set of precise instructions for performing computation.
Infinite
Finite
Constant
None of the mentioned
Explanation:
By the definition of an algorithm.