Are you looking for Nptel Design and analysis of algorithms Week 2 Quiz Answers? You are here at right place for Nptel assignment answers.
Table of Contents
Design and analysis of algorithms Week 2 Quiz Answers
Design and analysis of algorithms Week 2 Quiz Answers (July-Dec 2025)
Q1.Consider the following variation of the merge function, where the input lists A and B are assumed to be sorted, with no duplicated elements, and C is the output list. What does C contain after executing StrangeMerge(A, m, B, n, C)? a) C contains the intersection of A and B. b) C contains all values in A that do not occur in B. c) C contains all values in B that do not occur in A. d) C contains all values that occur in either A or B, but not in both input lists.
Q2.Suppose we modify mergesort as follows: We split the input into three equal segments, recursively sort each segment, and then do a 3-way merge. What can we say about the asymptotic worst-case complexity of this 3-way mergesort compared to the usual mergesort? a) The asymptotic worst-case complexity of 3-way mergesort is the same as that of usual mergesort. b) The asymptotic worst-case complexity of 3-way mergesort is better than that of usual mergesort. c) The asymptotic worst-case complexity of 3-way mergesort is worse than that of usual mergesort. d) This depends on the length and the initial arrangement of values of the input.
Q3.Suppose a new generation CPU can process 10¹⁰ operations per second. You have to sort an array with 10⁸ elements. Which of the following is true? a) Insertion sort will always take several hours while merge sort will always take less than 1 second. b) Quicksort will always take several hours while merge sort will always take less than 1 second. c) Insertion sort could take several hours while merge sort will always take less than 1 second. d) Insertion sort could take several hours while quicksort will always take less than 1 second.
Q4.Which of the following statements is not true about quicksort? a) For every fixed strategy to choose a pivot for quicksort, we can construct a worst-case input that requires time O(n²). b) If we could find the median in time O(n), quicksort would have worst-case complexity O(n log n). c) Quicksort and mergesort are both examples of divide and conquer algorithms. d) If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
Q5.We have a list of 3D points:[(7,8,1),(3,7,5),(6,4,1),(6,9,5),(0,5,2),(9,9,0)]. We sort these in ascending order by the third coordinate. Which of the following corresponds to a stable sort of this input? a) [(9,9,0), (7,8,1), (6,4,1), (0,5,2), (3,7,5), (6,9,5)] b) [(9,9,0), (7,8,1), (6,4,1), (0,5,2), (6,9,5), (3,7,5)] c) [(0,5,2), (3,7,5), (6,4,1), (6,9,5), (7,8,1), (9,9,0)] d) [(9,9,0), (6,4,1), (7,8,1), (0,5,2), (3,7,5), (6,9,5)]
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(nlogn)O(n \log n). b) The average-case behavior is O(nlogn)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(nlogn)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(nlogn)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?
