1. Which of the following searching algorithm is fastest when the input array is not sorted but has uniformly distributed values?
a) jump search
b) linear search
c) binary search
d) interpolation search
Explanation: Out of the given options linear search is the only searching algorithm which can be applied to arrays which are not sorted. It has a time complexity of O(n) in the worst case.
2. Interpolation search is an in place algorithm.
a) true
b) false
Explanation: Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.
3. Interpolation search has a better time complexity than exponential search for any given array.
a) True
b) False
Explanation: The worst case time complexity of interpolation search and exponential search are O(n) and O(log n) respectively. So exponential search is better when the worst case scenario is considered.
4. What are the updated values of high and low in the array if the element being searched is greater than the value at calculated index in interpolation search? (pos = current position)
a) low = pos + 1, high remains unchanged
b) high = pos – 1, low remains unchanged
c) low = low +1, high = high – 1
d) low = pos +1, high = pos – 1
Explanation: When the element being searched is greater than the value at the calculated position then in that case we update low and high remains unaltered. Updated value of low is low = pos + 1.
5. What are the updated values of high and low in the array if the element being searched is lower than the value at calculated index in interpolation search? (pos = current position)
a) low = pos + 1, high remains unchanged
b) high = pos – 1, low remains unchanged
c) low = low +1, high = high – 1
d) low = pos +1, high = pos – 1
Explanation: When the element being searched is lower than the value at the calculated position then in that case we update high and low remains unaltered. Updated value of high is high = pos – 1.
6. How many passes does an insertion sort algorithm consist of?
a) N
b) N-1
c) N+1
d) N2
Explanation: An insertion algorithm consists of N-1 passes when an array of N elements is given
7. Which of the following algorithm implementations is similar to that of an insertion sort?
a) Binary heap
b) Quick sort
c) Merge sort
d) Radix sort
Explanation: Insertion sort is similar to that of a binary heap algorithm because of the use of temporary variable to swap.
8. What is the average case running time of an insertion sort algorithm?
a) O(N)
b) O(N log N)
c) O(log N)
d) O(N2)
Explanation: The average case analysis of a tight bound algorithm is mathematically achieved to be O(N2).
9. Any algorithm that sorts by exchanging adjacent elements require O(N2) on average.
a) True
b) False
Explanation: Each swap removes only one inversion, so O(N2) swaps are required.
10. What is the average number of inversions in an array of N distinct numbers?
a) N(N-1)/4
b) N(N+1)/2
c) N(N-1)/2
d) N(N-1)/3
Explanation: The total number of pairs in a list L is N(N-1)/2. Thus, an average list has half this amount, or N(N-1)/4 inversions.
Design and Analysis of Algorithms
The Basics: Sorting Made Simple
Imagine you're a librarian with a stack of books in a chaotic order. Now, your goal is to arrange them neatly on the shelves. What do you do? You pick up a book, compare it with the ones already on the shelf, and find its perfect spot – that's Insertion Sort in a nutshell!
Step by Step Elegance
1. Picking Partners: Insertion Sort takes each element and places it where it belongs, one at a time. No VIP treatment here, every element gets its moment in the spotlight.
2. Jigsaw Puzzle: It's like solving a jigsaw puzzle. You start with one piece, fitting it snugly, and then proceed with the next until the picture is complete.
3. Back to Basics: This algorithm is your algorithmic grandma, reminding you of the good old days when life was simpler. It's not fancy, but boy, does it get the job done!
Why Insertion Sort?
Efficiency in Small Doses: While it might not be your go-to for massive datasets, Insertion Sort shines when dealing with smaller arrays.
Adaptive Nature: Insertion Sort is like a chameleon – it adapts. If elements are nearly sorted, it becomes an algorithmic ninja, swift and efficient.
Memory Saver: If you're tight on memory, Insertion Sort is your friend. It's lightweight and won’t hog your system resources.
So, there you have it – Insertion Sort, the unsung hero of sorting algorithms, and a sneak peek into conquering Design and Analysis of Algorithms MCQs. Now, go forth, sort those algorithms, and ace those quizzes! Happy coding!