Discrete Mathematics

Algorithms

Question 1
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 2
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 3
Marks : +2 | -2
Pass Ratio : 100%
The complexity of linear search algorithm is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity of linear search is O(n).
Question 4
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 5
Marks : +2 | -2
Pass Ratio : 100%
Is 17 congruent to 4 modulo 6.
True
False
Explanation:
6 does not divide 17 – 4 = 13.
Question 6
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.
Question 7
Marks : +2 | -2
Pass Ratio : 100%
The quotient and remainder when -1 is divided by 3 is?
-1 and -1
-1 and 2
1 and 2
-1 and -2
Explanation:
According to the Division Algorithm -1 = 3(-1) + 2. Hence, quotient when -1 divided by 3 is -1 = -1 div 3 and remainder when -1 divided by 3 is 2 = -1 mod 3.
Question 8
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 9
Marks : +2 | -2
Pass Ratio : 100%
The complexity of Binary search algorithm is _________
O(n)
O(log)
O(n2)
O(n log n)
Explanation:
The compexity of binary search is O(logn).
Question 10
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.