## 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
^{2}) - O(n
^{2}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
^{2}) - 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?

- [(39,10,93),(13,25,75),(16,25,93),(30,32,55),(27,61,81),(16,61,42)]
- [(39,10,93),(16,25,93),(13,25,75),(30,32,55),(16,61,42),(27,61,81)]
- [(39,10,93),(13,25,75),(16,25,93),(30,32,55),(16,61,42),(27,61,81)]
- [(39,10,93),(16,25,93),(13,25,75),(30,32,55),(27,61,81),(16,61,42)]

Answer :-Click Here