1. Which of the following false about Jump Search?
a) Jump Search is better than Linear Search
b) Useful when jumping back is more costly than jumping forward
c) Jump Search is worse than Binary Search
d) Jump search starts from the index 0 even though specified index is k
Explanation: Linear search has O(n) complexity and Binary search has O(logn) complexity, in Jump search you have to jump backwards only once, hence it is preferable if jumping backwards is costly. Jump search starts from index k (specified index) and searches for the element. It won’t start searching from index 0.
2. Which algorithmic technique does Fibonacci search use?
a) Brute force
b) Divide and Conquer
c) Greedy Technique
d) Backtracking
Explanation: With every iteration, we divide the given array into two sub arrays(not necessarily equal).
3. Choose the recursive formula for the Fibonacci series.(n>=1)
a) F(n) = F(n+1) + F(n+2)
b) F(n) = F(n) + F(n+1)
c) F(n) = F(n-1) + F(n-2)
d) F(n) = F(n-1) – F(n-2)
Explanation: F(n) = F(n-1) + F(n-2)
4. What is the time complexity of Fibonacci Search?
a) O(logn)
b) O(n)
c) O(n2)
d) O(nlogn)
Explanation: Since it divides the array into two parts, although not equal, its time complexity is O(logn), it is better than binary search in case of large arrays.
5. Which of the following is not an advantage of Fibonacci Search?
a) When the element being searched for has a non uniform access storage
b) Can be used in magnetic tapes
c) Can be used for large arrays which do not fit in the CPU cache or in the RAM
d) It can be applied efficiently on unsorted arrays
Explanation: When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. Fibonacci search won’t work on unsorted arrays. The input should be a sorted array or array should be sorted before Fibonacci search.
6. What is the length of the step in jump search?
a) n
b) n/2
c) sqrt(n)
d) 1
Explanation: If the step size is 1, it becomes a linear search, if it is n, we reach the end of the list in just on step, if it is n/2, it becomes similar to binary search, therefore the most efficient step size is found to be sqrt(n).
7. What is the time complexity of Jump Search?
a) O(logn)
b) O(n)
c) O(sqrt(n))
d) O(nlogn)
Explanation: Since the size of the step is sqrt(n), the complexity is also obviously O(sqrt(n)).
8. Exponential search algorithm requires which of the following condition to be true?
a) array should be sorted
b) array should have not be sorted
c) array should have a less than 128 elements
d) array should be partially sorted
Explanation: Exponential sort requires the input array to be sorted. The algorithm would fail to give the correct result if array is not sorted.
9. Which of the following searching algorithm is used with exponential sort after finding the appropriate range?
a) Linear search
b) Binary search
c) Jump search
d) Fibonacci Search
Explanation: In exponential search, we first find a range where the required elements should be present in the array. Then we apply binary search in this range.
10. Exponential search has ____________
a) neither an exponential space complexity nor exponential time complexity
b) exponential time complexity but a linear space complexity
c) exponential space complexity but a linear time complexity
d) both exponential time and space complexity
Explanation: Exponential search has neither an exponential space complexity nor exponential time complexity. It is named exponential search because it searches for an element in an exponential manner.
Design and Analysis of Algorithms
Fibonacci – Not Just a Sequence of Numbers
We all know Fibonacci from the number sequence, but did you know it's also a rockstar in the world of algorithms? This search technique is like the magician of the algorithmic circus, performing tricks to find that elusive needle in a haystack.
The MCQ Maze and Fibonacci’s GPS
Imagine you're lost in a multiple-choice question maze, desperately seeking the correct answer. Enter Fibonacci, your algorithmic GPS. It efficiently guides you through the options, narrowing down possibilities with the grace of a mathematical ballet.
The Dance of Golden Ratios
Fibonacci isn't just about numbers; it's about ratios and a symphony of precision. In algorithmic terms, it elegantly divides and conquers, optimizing the search process like a maestro conducting a symphony.
Designing Paths with Fibonacci Elegance
When it comes to algorithmic design, Fibonacci adds a touch of elegance. It crafts paths through the algorithmic wilderness with a flair that would make even the most seasoned explorer envious. Think of it as the Indiana Jones of algorithms, navigating through the intricacies with style.
Cracking the Code with Fibonacci Pizzazz
In the world of MCQs and algorithmic challenges, you need a secret weapon. Fibonacci is that sly fox, helping you crack the code with its pizzazz and mathematical charm. It's the Sherlock Holmes of algorithms, solving mysteries one step at a time.
Conclusion: Fibonacci – Your Algorithmic Sidekick
As we wrap up our rendezvous with the Fibonacci search, it's clear that this algorithm isn't just a sequence of numbers; it's a whimsical sidekick in the grand adventure of algorithmic design. So, the next time you're lost in the labyrinth of MCQs, let Fibonacci be your guide – the superhero of design and analysis of algorithms!
Remember, in the algorithmic universe, Fibonacci is not just a number; it's the magic wand that turns complexity into simplicity. Happy coding, and may the Fibonacci force be with you!