Design and analysis of algorithms Nptel Week 2 Quiz Answers

Are you looking for Nptel Design and analysis of algorithms Week 2 Quiz Answers? You are here at right place for Nptel assignment answers.

Course link: Click here

Design and analysis of algorithms Week 2 Quiz Answers (Jan-Apr 2025)

Having collected Aadhaar information for each SIM card, a government agency wants to check that all the Aadhaar numbers entered in SIM card applications are actually valid, by comparing SIM card applications against the list of registered Aadhaar numbers. Which of the following is likely to be the best strategy for this?
a) Use a nested loop. For each SIM card application S, and for each Aadhaar number A, check if the Aadhaar number listed in S is the same as A.
b) Sort the SIM card applications and use binary search to speed up the process.
c) Sort the registered Aadhaar numbers and use binary search to speed up the process.
d) Sort both the SIM card applications and registered Aadhaar numbers and merge the two lists.

Suppose our aim is to sort an array in descending order. Which of the following statements is true?
a) Input in ascending order is the worst case for both selection sort and insertion sort.
b) Input in ascending order is the worst case for insertion sort but not for selection sort.
c) Input in descending order is the worst case for both selection sort and insertion sort.
d) Input in ascending order is the worst case for selection sort but not for insertion sort.

Suppose we want to sort an array in ascending order. We have a stable implementation of quicksort that alternately chooses the first and last element of the array as the pivot with each recursive call. Which of the following is not true for this implementation?
a) The worst-case behavior is O(nlog⁡n)O(n \log n).
b) The average-case behavior is O(nlog⁡n)O(n \log n).
c) The worst-case behavior is O(n2)O(n^2).
d) The average-case behavior is asymptotically better than the worst-case behavior.

Which of the following statements is not true?
a) Quicksort and merge sort are both examples of divide and conquer algorithms.
b) If we randomly choose a pivot element each time, quicksort will always terminate in time O(nlog⁡n)O(n \log n).
c) For every fixed strategy to choose a pivot for quicksort, we can construct a worst-case input that requires time O(n2)O(n^2).
d) If we could find the median in time O(n)O(n), quicksort would have a worst-case complexity of O(nlog⁡n)O(n \log n).

We have a list of pairs where each pair consists of a student’s name and his/her marks in a course. We sort these pairs in ascending order of marks. Which of the following corresponds to a stable sort of this input?