NPTEL Design and Analysis of Algorithms Week 2 Assignment Answers 2024

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(n2)
• O(n2 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(n2)
• 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`