NPTEL Design and Analysis of Algorithms Week 2 Assignment Answers 2024

1. 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.

function MysteryMerge(A,m,B,n,C) {
  // A has m elements, B has n elements
  i = 0; j = 0; k = 0;
  while (i+j < m+n) {
    if (i == m) {j++;}
    if (j == n) {C[k] = A[i]; i++; k++;}
    if (i < m and j < n) {
       if (A[i] < B[j]) {C[k] = A[i]; i++; k++;}
       if (A[i] == B[j]) {i++; j++;}
       if (A[i] > B[j]) {j++;}
    }
  }
}

What does C contain after executing MysteryMerge(A,m,B,n,C)?

C contains the intersection of A and B.
C contains all values in A that do not occur in B.
C contains all values in B that do not occur in A.
C contains all values that occur in either A or B, but not in both input lists.

Answer :- Click Here

2. We have 8 sorted lists, each of length n. We need to merge them into a single sorted list. We merge them in pairs to get 4 sorted lists of length 2n, then 2 sorted lists of length 4n and finally 1 sorted list of length 8n. What is the complexity of this procedure?

O(n)
O(n log n)
O(n²)
O(n² log n)

Answer :- Click Here

3. You are testing an application to remove duplicate voters that works as follows. It first sorts the voter list and then does a linear scan for identical adjacent entries. Your test is running on a CPU that can process 109 operations per second. You observe that for cities with 500,000 voters, the application sometimes takes a few minutes to respond. Which of the following is a valid conclusion about the algorithm used for sorting?

It could be insertion sort, but is definitely not quicksort or mergesort.
It could be insertion sort or quicksort, but is definitely not mergesort.
It could be insertion sort or merge sort, but is definitely not quicksort.
It could be any of insertion sort, quicksort or merge sort.

Answer :-

4. Which of the following statements is not true about quicksort?

For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n²)
If we could find the median in time O(n), quicksort would have worst case complexity O(n log n)
If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
Quicksort and merge sort are both examples of divide and conquer algorithms.

Answer :- Click Here

5. We have a list of three dimensional points [(39,10,93),(27,61,81),(16,25,93),(30,32,55),(16,61,42),(13,25,75)] We sort these in ascending order by the second coordinate. Which of the folllowing corresponds to a stable sort of this input?