Design And Analysis Of Algorithms Set 4

Computer Science Engineering (CSE)

Practice Mode Previous Next
On This Page

This set of Design and Analysis of Algorithms Multiple Choice Questions & Answers (MCQs) focuses on Design And Analysis Of Algorithms Set 4

Q1 | Tower of hanoi problem can be solved iteratively.
  • true
  • false
Answer: true
Explaination:
iterative solution to tower of hanoi puzzle also exists. its approach depends on whether the total numbers of disks are even or odd.
Q2 | Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be                      
  • 15 seconds
  • 30 seconds
  • 16 seconds
  • 32 seconds
Answer: 30 seconds
Explaination:
number of moves = 24-1=16- 1=15
Q3 | Master’s theorem is used for?
  • solving recurrences
  • solving iterative relations
  • analysing loops
  • calculating the time complexity of any code
Answer: solving recurrences
Explaination:
master’s theorem is a direct method for solving recurrences. we can solve any recurrence that falls under any one of the three cases of master’s theorem.
Q4 | How many cases are there under Master’s theorem?
  • 2
  • 3
  • 4
  • 5
Answer: 3
Explaination:
there are primarily 3 cases under master’s theorem. we can solve any recurrence that falls under any one of these three cases.
Q5 | What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
  • none of the below
  • t(n) = o(nc log n)
  • t(n) = o(f(n))
  • t(n) = o(n2)
Answer: t(n) = o(nc log n)
Explaination:
in second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n) = o(nc log n)
Q6 | What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc?
  • none of the below
  • t(n) = o(nc log n)
  • t(n) = o(f(n))
  • t(n) = o(n2)
Answer: t(n) = o(f(n))
Explaination:
in third case of master’s theorem the necessary condition is that c > logba. if this condition is true then t(n) = o(f(n)).
Q7 | We can solve any recurrence by using Master’s theorem.
  • true
  • false
Answer: false
Explaination:
no we cannot solve all the recurrences by only using master’s theorem. we can solve only those which fall under the three cases prescribed in the theorem.
Q8 | Under what case of Master’s theorem will the recurrence relation of merge sort fall?
  • 1
  • 2
  • 3
  • it cannot be solved using master’s theorem
Answer: 2
Explaination:
the recurrence relation of merge sort is given by t(n) = 2t(n/2) + o(n). so we can observe that c = logba so it will fall under case 2 of master’s theorem.
Q9 | Under what case of Master’s theorem will the recurrence relation of stooge sort fall?
  • 1
  • 2
  • 3
  • it cannot be solved using master’s theorem
Answer: 1
Explaination:
the recurrence relation of stooge sort is given as t(n) = 3t(2/3n) + o(1). it is found too be equal to o(n2.7) using master’s theorem first case.
Q10 | Which case of master’s theorem can be extended further?
  • 1
  • 2
  • 3
  • no case can be extended
Answer: 2
Explaination:
the second case of master’s theorem can be extended for a case where f(n)
Q11 | What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k?
  • none of the below
  • t(n) = o(nc log n)
  • t(n)= o(nc (log n)k+1
  • t(n) = o(n2)
Answer: t(n)= o(nc (log n)k+1
Explaination:
in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1.
Q12 | Under what case of Master’s theorem will the recurrence relation of binary search fall?
  • 1
  • 2
  • 3
  • it cannot be solved using master’s theorem
Answer: 2
Explaination:
the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem.
Q13 | 7 T (n/2) + 1/n
  • t(n) = o(n)
  • t(n) = o(log n)
  • t(n) = o(n2log n)
  • cannot be solved using master’s theorem
Answer: cannot be solved using master’s theorem
Explaination:
the given recurrence cannot be solved by using the master’s theorem. it is because in this recurrence relation a < 1 so master’s theorem cannot be applied.
Q14 | What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)?
  • o(n)
  • o(n*m)
  • o(m)
  • o(log n)
Answer: o(m)
Explaination:
kmp algorithm is an efficient pattern searching algorithm. it has a time complexity of o(m) where m is the length of text.
Q15 | What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
  • o(n + m)
  • o(m)
  • o(n)
  • o(m * n)
Answer: o(n + m)
Explaination:
z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it has a time complexity of o(m + n) where m is the length of text and n is the length of the pattern.
Q16 | What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)?
  • o(n + m)
  • o(m)
  • o(n)
  • o(m * n)
Answer: o(m)
Explaination:
z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it an auxiliary space of o(m) for maintaining z array.
Q17 | The naive pattern searching algorithm is an in place algorithm.
  • true
  • false
Answer: true
Explaination:
the auxiliary space complexity required by naive pattern searching algorithm is o(1). so it qualifies as an in place algorithm.
Q18 | Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity.
  • true
  • false
Answer: true
Explaination:
the worst case time complexity of rabin karp algorithm is o(m*n) but it has a linear average case time complexity. so rabin karp and naive pattern searching algorithm have the same worst case time complexity.
Q19 | Which of the following sorting algorithms is the fastest?
  • merge sort
  • quick sort
  • insertion sort
  • shell sort
Answer: quick sort
Explaination:
quick sort is the fastest known sorting algorithm because of its highly optimized inner loop.
Q20 | Quick sort follows Divide-and-Conquer strategy.
  • true
  • false
Answer: true
Explaination:
in quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy).
Q21 | What is the worst case time complexity of a quick sort algorithm?
  • o(n)
  • o(n log n)
  • o(n2)
  • o(log n)
Answer: o(n2)
Explaination:
the worst case performance of a quick sort algorithm is mathematically found to be o(n2).
Q22 | Which of the following methods is the most effective for picking the pivot element?
  • first element
  • last element
  • median-of-three partitioning
  • random element
Answer: median-of-three partitioning
Explaination:
median-of-three partitioning is the best method for choosing an appropriate pivot element. picking a first, last or random element as a pivot is not much effective.
Q23 | Which is the safest method to choose a pivot element?
  • choosing a random element as pivot
  • choosing the first element as pivot
  • choosing the last element as pivot
  • median-of-three partitioning method
Answer: choosing a random element as pivot
Explaination:
this is the safest method to choose the pivot element since it is very unlikely that a random pivot would consistently provide a poor partition.
Q24 | What is the average running time of a quick sort algorithm?
  • o(n2)
  • o(n)
  • o(n log n)
  • o(log n)
Answer: o(n log n)
Explaination:
the best case and average case analysis of a quick sort algorithm are mathematically found to be o(n log n).
Q25 | Which of the following sorting algorithms is used along with quick sort to sort the sub arrays?
  • merge sort
  • shell sort
  • insertion sort
  • bubble sort
Answer: insertion sort
Explaination:
insertion sort is used along with quick sort to sort the sub arrays.
Previous Next