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 StrangeMerge(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) {C[k] = B[j]; j++; k++;}
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]) {C[k] = B[j]; j++; k++;}
}
}
What does C contain after executing StrangeMerge(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.
2. Suppose we modify mergesort as follows. We split the input into three equal segments, recursively sort each segment and then do a three way merge of the three sorted segments to obtain a fully sorted output.
If we work out the recurrence for this variant, we find that the worst case complexity is O(n log3 n), as opposed to O(n log2 n) for the usual divide and conquer that splits the input into two equal segments.
Let us call the new version 3-way mergesort. What can we say about the asymptotic worst case complexity of 3-way-mergesort with the usual mergesort?
The asymptotic worst case complexity of 3-way mergesort is the same as that of usual mergesort.
The asymptotic worst case complexity of 3-way mergesort is better than that of usual mergesort.
The asymptotic worst case complexity of 3-way mergesort is worse than that of usual mergesort.
This depends on the length and the initial arrangement of values of the input.
3. Suppose a new generation CPU can process 1010 operations per second. You have to sort an array with 108 elements. Which of the following is true?
Insertion sort will always take several hours while merge sort will always take less than 1 second.
Quicksort will always take several hours while merge sort will always take less than 1 second.
Insertion sort could take several hours while merge sort will always take less than 1 second.
Insertion sort could take several hours while quicksort will always take less than 1 second.
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).
Quicksort and merge sort are both examples of divide and conquer algorithms.
If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
5. We have a list of three dimensional 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 folllowing corresponds to a stable sort of this input?
[(9,9,0),(7,8,1),(6,4,1),(0,5,2),(3,7,5),(6,9,5)]
[(9,9,0),(7,8,1),(6,4,1),(0,5,2),(6,9,5),(3,7,5)]
[(0,5,2),(3,7,5),(6,4,1),(6,9,5),(7,8,1),(9,9,0)]
[(9,9,0),(6,4,1),(7,8,1),(0,5,2),(3,7,5),(6,9,5)]