Discrete Mathematics

Algorithms

Question 1
Marks : +2 | -2
Pass Ratio : 100%
Is 102 congruent to 6 modulo 16.
True
False
Explanation:
16 divide 102 – 6 = 96.
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%
The complexity of merge sort algorithm is _________
O(n)
O(log n)
O(n2)
O(n log n)
Explanation:
The worst case complexity for merge sort is O(nlogn).
Question 4
Marks : +2 | -2
Pass Ratio : 100%
Out of the following which property algorithms does not share?
Input
Finiteness
Generality
Constancy
Explanation:
All the others are the properties of algorithms.
Question 5
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 6
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 7
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 complexity of Bubble sort algorithm is O(n2).
Question 8
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 9
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 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.