NPTEL Design and analysis of algorithms Assignment 2 Answer

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++;}
    }
  }
}

ans - 13

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

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?

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 10⁹ 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?

Which of the following statements is not true about quicksort?

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?