Unit- II
Q.1
Indicator random Variables provide a convenient method for Converting
[A]Probabilities
[B]Expectation
[C]Both [A] and [B]
[D]
None of these
Q.2 ........is the use of probability in the
analysis of problems.
[A]Probabilistic analysis
[B]Worst
case analysis
[C]Best
case Analysis
[D]None
of these
Q.3
What is the best case complexity of binary search in successful search?
[A]
θ(n log n)
[B]
(θlog n)
[C] θ(1)
[D]
θ(n)
Q.4 What will be the worst case time complexity
of merge sort?
[A] O(n log n)
[B]
O(n²)
[C]
O(n² log n)
[D]
O(n log n²)
Q.5
Which of the following method is used for sorting in quick sort?
[A]
merging
[B] partitioning
[C]
selection
[D]
exchanging
Q.6
What is time complexity for best case of Quick Sort?
[A] O(n log n)
[B]
O(n²)
[C]
O(n² log n)
[D]
O(n log n²)
Q.7
The running time depend on
[A] partition is balanced or
unbalance
[
B] input array
[C]
pivot element position
[D]
None of these
Q.8 An algorithm .......if its behaviour is
determined not only by its input but also by values produced by random number
generator.
[A]Sequential
[B]Randomized
[C]Parallel
[D]None
of these
Q.9
The algorithm from which the input is random by referring to the running time
of a ....................as an expected running time.
[A]Randomized algorithm
[B]
Merge sort
[C]Bubble
sort
[D]
None of these
Q.10
What is the worst case time complexity of a quick sort algorithm?
[A]
O(n)
[B]
O(n log n)
[C] O(n²)
[D]
O(log n)
Q.11
Which of the following sorting algorithms is the fastest?
[A]
Merge sort
[B] Quick sort
[C]
Insertion sort
[D]
Shell sort
Q.12
Identify problem in which All permutations of the input are equally likely, a
probabilistic analysis?
[A]
TSP problem
[B]Hiring problem
[C]
Greedy problem
[D]
None of these
Q.13
Merge sort uses which of the following technique to implement sorting?
[A]
backtracking
[B]
greedy algorithm
[C] divide and conquer
[D]
dynamic programming
Q.14
What is the advantage of recursive approach than an iterative approach?
[A]
Consumes less memory
[B] Less code and easy to implement
[C]
Consumes more memory
[D]
More code has to be written
Q.15
Which of the following is not an application of binary search?
[A] To find the lower/upper bound in an
ordered sequence
[B]
Union of intervals
[C]
Debugging
[D] To search in unordered list
Q.16
Find the pivot element from the given input using median-of-three partitioning
method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.
[A] 8
[B]
7
[C]
9
[D] 6
Q.17
A randomized algorithm uses random bits as input inorder to achieve a
_____________ good performance over all possible choice of random bits.
[A]
worst case
[B]
best case
[C] average case
[D]
none of the mentioned
Q.18
................... is the use of probability in the analysis of problems.
[A] Probabilistic analysis
[B]Linear
Analysis
[C]Quadratic
Analysis
[D]
None of these
Q.19
In Hiring Algorithm if candidate i is better than candidate best
[A]
best=0
[B]best=i
[C]
best=1
[D]
None of these
Q.20 Worst case analysis of Hiring Algorithm is
[A] O(Chm)
[B]
O(Cin+Chm)
[C]
O(CiN)
[D]
None of these
Q.21 Each of the possible n! permutations appears
with equal probability then it is
[A] uniform random permutation
[B]
random permutation
[C]
uniform permutation
[D] permutation
Q.22
Which algorithm provide a convenient method for converting between
probabilities and expectations?
[A]
Quick sort
[B] Indicator random variables
[C]
Bubble sort
[D]
None of these
Q.23
What is a randomized QuickSort?
[A] The leftmost element is chosen as the
pivot
[B]
The rightmost element is chosen as the pivot
[C]
Any element in the array is chosen as the pivot
[D] A random number is generated
which is used as the pivot
Q.24
Choose the incorrect statement about merge sort from the following?
[A]
it is a comparison based sort
[B] it is an adaptive algorithm
[C]
it is not an in place algorithm
[D]
it is stable algorithm
Q.25
Indicator random variable denoted by
[A] I{A}
[B]
R{s}
[C]
V{a}
[D]
None of these
Q.26
What is the time complexity of uniform
binary search?
[A]
O(nlogn)
[B] O(logn)
[C]
O(n)
[D]
O(n²)
Q.27
In which of the cases uniform binary search fails compared to binary search?
[A] A table lookup is generally faster than an
addition and a shift
[B]
Many searches will be performed on the same array
[C]
Many searches will be performed on several arrays of the same length
[D] Complexity of code
Q.28
Which of the following stable sorting algorithm takes the least time when
applied to an almost sorted array?
[A]
Quick sort
[B]
Insertion sort
[C]
Selection sort
[D]
Merge sort
Q.29
Which of the following is not in place sorting algorithm by default?
[A] merge sort
[B]
quick sort
[C]
heap sort
[D]
insertion sort
Q.30
Choose the correct statement about bottom up merge sort from the following?
[A] bottom up merge sort has greater time
complexity than standard merge sort
[B]
bottom up merge sort has lesser time complexity than standard merge sort
[C] bottom up merge sort saves
auxiliary space required on call stack
[D] bottom up merge sort uses recursion.