1. The array is as follows: 1,2,3,6,8,10. At what time the element 6 is found? (By using linear search(recursive) algorithm)
a) 4th call
b) 3rd call
c) 6th call
d) 5th call
Explanation: Provided that the search starts from the first element, the function calls itself till the element is found. In this case, the element is found in 4th call.
2. The array is as follows: 1,2,3,6,8,10. Given that the number 17 is to be searched. At which call it tells that there’s no such element? (By using linear search(recursive) algorithm)
a) 7th call
b) 9th call
c) 17th call
d) The function calls itself infinite number of times
Explanation: The function calls itself till the element is found. But at the 7th call it terminates as goes outside the array.
3. What is the best case runtime of linear search(recursive) algorithm on an ordered set of elements?
a) O(1)
b) O(n)
c) O(logn)
d) O(nx)
Explanation: The best case occurs when the given element to be found is at the first position. Therefore O(1) is the correct answer.
4. Can linear search recursive algorithm and binary search recursive algorithm be performed on an unordered list?
a) Binary search can’t be used
b) Linear search can’t be used
c) Both cannot be used
d) Both can be used
Explanation: As binary search requires comparison, it is required that the list be ordered. Whereas this doesn’t matter for linear search.
5. What is the recurrence relation for the linear search recursive algorithm?
a) T(n-2)+c
b) 2T(n-1)+c
c) T(n-1)+c
d) T(n+1)+c
Explanation: After each call in the recursive algorithm, the size of n is reduced by 1. Therefore the optimal solution is T(n-1)+c.
6. 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
Explanation: A recursive approach is easier to understand and contains fewer lines of code.
7. Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
a) 5
b) 2
c) 3
d) 4
Explanation: level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
8. Given an array arr = {45,77,89,90,94,99,100} and key = 99; what are the mid values(corresponding array elements) in the first and second levels of recursion?
a) 90 and 99
b) 90 and 94
c) 89 and 99
d) 89 and 94
Explanation: At first level key = 90
At second level key= 99
Here 90 and 99 are mid values.
9. What is the worst case complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: Using the divide and conquer master theorem.
10. What is the average case time complexity of binary search using recursion?
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
Explanation: T(n) = T(n/2) + 1, Using the divide and conquer master theorem.
Design and Analysis of Algorithms
The Quest for the Right Element
Imagine you're at a library, searching for that one book that holds the answer to all your questions. Linear search is like being a meticulous librarian, scanning each shelf one by one until you lay your hands on the elusive tome.
Linear search is the algorithmic equivalent of a sequential investigation. It's like looking for your keys – you check each pocket until you triumphantly declare, "Eureka!"
Why Linear, You Ask?
Linear search might not be the rockstar of algorithms, but it has its moment in the spotlight. You have an unordered list, and you need to find a specific element. Linear search steps in, traversing the list like a detective on a mission.
It's the go-to method when you're dealing with a small-scale scavenger hunt. Efficient? Not for colossal datasets. But for a cozy little array, it's your trusty sidekick.
Playing the Algorithmic Detective
Think of linear search as Sherlock Holmes in the algorithmic universe. It meticulously examines each clue, eliminating impostors until it finds the genuine article. It might not be the flashiest detective, but it gets the job done.
In the MCQ arena of Design and Analysis of Algorithms, questions often throw you into a maze of choices. Linear search, with its methodical approach, can be your Watson, leading you to the correct answer step by step.
Wrapping It Up
So, there you have it – Linear Search, the modest hero in the algorithmic saga. It might not make headlines, but it's an indispensable part of the design and analysis party, especially when tackling MCQ challenges. As we bid adieu to our algorithmic adventure, remember: sometimes, the simplest path leads to the most profound discoveries. Happy coding, fellow algorithm explorers!