Discrete Mathematics

Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
The complexity of Bubble sort algorithm is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity for Bubble sort is O(n2) and best case is O(n).
Question 2
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 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%
Is 102 congruent to 6 modulo 16.
True
False
Explanation:
16 divide 102 – 6 = 96.
Question 5
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 6
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).
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 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 9
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 10
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.