Discrete Mathematics

Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The quotient when 19 is divided by 6 is?
1
2
3
0
Explanation:
According to the Division Algorithm 19 = 6(3) + 1. Hence, quotient when 19 divided by 6 is 3 = 19 div 6.
Question 2
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 3
Marks : +2 | -2
Pass Ratio : 100%
To sort a list with n elements, the insertion sort begins with the __________ element.
First
Second
Third
Fourth
Explanation:
The insertion sort compares the second element with the first element to start sorting.
Question 4
Marks : +2 | -2
Pass Ratio : 100%
The remainder when 111 is divided by 12 is?
0
1
2
3
Explanation:
According to the Division Algorithm 111 = 12(9) + 3. Hence, remainder when 111 divided by 12 is 3 = 111 mod 12.
Question 5
Marks : +2 | -2
Pass Ratio : 100%
The value of 12 mod 3 is?
0
1
2
3
Explanation:
By the Division algorithm 12 = 3(4) + 0. Where remainder is 12 mod 3.
Question 6
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 7
Marks : +2 | -2
Pass Ratio : 100%
The worst case complexity for insertion sort is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
In worst case nth comparison are required to insert the nth element into correct position.
Question 8
Marks : +2 | -2
Pass Ratio : 100%
The value of 15 mod 11 is?
1
2
3
4
Explanation:
By the Division algorithm 15 = 11(1) + 4. Where the remainder is 15 mod 11.
Question 9
Marks : +2 | -2
Pass Ratio : 100%
Which of the following case does not exist in complexity theory?
Best case
Worst case
Average case
Null case
Explanation:
Null case does not exist in complexity Theory.
Question 10
Marks : +2 | -2
Pass Ratio : 100%
The worst case complexity of quick sort is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity of quick sort is O(n2).