Practice Midterm Flashcards
We consider quicksort with the auxiliary procedure for partition. Suppose that partition splits the array always in a 11-to-1 proportional split, so one part has length 1/12 and the other part has length 11/12. Then we have the following:
A) The recurrence for the running time of quicksort is T(n)= T(n/12) + T(11n/12) + cn with c a constant, and quicksort runs hence in O(n log n) time.
B) The recurrence for the running time of quicksort is T(n) = 2T(n/2) +cn with c a constant, and quicksort runs hence in O(n log n) time.
C) The recurrence for the running time of quicksort is T(n) = 12T(n/12) + cn with c a constant, and quicksort runs hence in O(n log n) time.
D) The recurrence for the running time of quicksort is T(n) = T(n/12) + T(11n/12) + cn with c a constant, and quicksort runs hence in O(n2) time.
A) The recurrence for the running time of quicksort is T(n)= T(n/12) + T(11n/12) + cn with c a constant, and quicksort runs hence in O(n log n) time.
We perform the procedure partition which is used in quicksort. The resulting array is [2, 3, 1, 4, 5, 8, 7, 9, 10]. Which are all keys that could have been the pivot?
A) 4, 5, 9, 10
B) 5, 9, 10
C) 4, 5, 8, 10
D) 4, 5, 8, 9, 10
A) 4, 5, 9, 10
Consider the pseudocode for partition. What is a drawback?
A) We have to traverse the array completely.
B) If the array is sorted, we swap every element with itself.
C) It contains a for-loop.
D) We use two indices.
B) If the array is sorted, we swap every element with itself.
Which of the following statements are true?
1) Heapsort is a divide-and-conquer algorithm.
2) Insertion sort can be faster than merge sort.
3) Heapsort is asymptotically optimal.
4) Bucket sort needs additional memory.
A) Only 2, 3, 4 are true.
B) Only 1, 2 are true.
C) Only 2, 3 are true.
D) Only 2, 4 are true.
A) Only 2, 3, 4 are true.
Which of the following statements are true?
1) Swapping two elements of an array can be done in constant time.
2) The smallest key of a max-heap is at the leftmost leaf.
3) All algorithms for turning an array into a max-heap are in Omega (n log(n)).
4) For all comparison-based sorting algorithms the worst-case time complexity is in Omega (n log(n)).
A) Only 1, 4 are true.
B) Only 1 is true.
C) Only 2 and 3 are true.
D) Only 1, 3, 4 are true.
E) Only 2, 3, 4 are true.
A) Only 1, 4 are true.
We perform the bottom-up procedure for building a max-heap. What is the result of performing (only) the first iteration of the for-loop on input A = [8, 1, 6, 4, 3, 7, 9]?
A) [8,1,9,4,3,7,6]
B) [8,4,9,1,3,7,6]
C) [9,1,6,4,3,7,8]
D) [9,1,8,4,3,7,6]
A) [8,1,9,4,3,7,6]
What is the result of adding the key 8 to the max-heap [9, 7, 4, 6, 5, 1, 3, 0, 0, 0 ] with heapsize 7?
A) [9, 7, 8, 6, 5, 1, 3, 4, 0, 0]
B) [8, 7, 4, 6, 5, 1, 9, 0, 0, 0]
C) [8, 7, 4, 6, 5, 1, 3, 9, 0, 0]
D) [9, 8, 4, 7, 5, 1, 3, 6, 0, 0]
D) [9, 8, 4, 7, 5, 1, 3, 6, 0, 0]
What does it mean that the lower-bound on the worst-case time complexity for comparison-based sorting is Omega (n log(n))?
A) It means that using comparison-based sorting we cannot sort faster than in n log(n).
B) It means that the worst-case of a comparison-based sorting algorithm is at least n log(n).
C) It means that the worst-case of a comparison-based sorting algorithm is at most n log(n).
D) It means that using comparison-based sorting we cannot sort slower than in n log(n).
B) It means that the worst-case of a comparison-based sorting algorithm is at least n log(n).
Which of the following recurrence equations with T(0) = 1 gives T(n) in Theta(n^2)?
A) T(n) = 2T(n/2) + n
B) T(n) = T(n-1) + 1
C) T(n) = T(n-1) + n
D) T(n) = T(n-1)
C) T(n) = T(n-1) + n
Which of the following is(are) in increasing rate of growth?
A) 2^7, n log(n), n^2, n!
B) 3n, 2^3, n log(n), n^3
C) n^2, n^3, n log(n), 2^n
D) n log(n), n^2, n^7, 2^n
E) n log(n), n^2, 2^7, n!
A) 2^7, n log(n), n^2, n!
D) n log(n), n^2, n^7, 2^n
What is a reason to use insertion sort as subroutine in bucket sort?
A) It has a good worst-case time complexity.
B) It has a good best-case time complexity.
C) It performs relatively well on small inputs.
D) It performs relatively well on lists.
C) It performs relatively well on small inputs.
Which of the following arrays is a max-heap?
A) [1,2,3,4,5,6,7]
B) [7,3,1,2,6,4,5]
C) [7,3,6,1,2,5,4]
D) [7,6,4,5,3,1,2]
E) [7,6,5,4,3,2,1]
F) [7,6,4,3,1,5,2]
C) [7,3,6,1,2,5,4]
D) [7,6,4,5,3,1,2]
E) [7,6,5,4,3,2,1]
What is the advantage of implementing a min-priority queue using a heap?
A) Removal is in constant time.
B) Adding is in constant time.
C) Adding and deleting are equally expensive.
D) Adding and deleting are both faster than if we use an array.
C) Adding and deleting are equally expensive.
We apply heapsort to an array where all n elements are the same. What is its performance in this case?
A) n log(n) because in the for-loop we execute n times MaxHeapify
B) n log(n) because half of the nodes are already max-heaps
C) n because in the for-loop we perform n times elementary time work
D) n because we can build a max-heap in linear time
D) n because we can build a max-heap in linear time
What is the best-case time complexity of selection sort?
A) O(1) because we find immediately the smallest elements of the unordered part.
B) O(n) because we just check whether the array is ordered.
C) O(n log(n)) because that is the best-case for comparison-based sorting.
D) O(n^2) because we always have to completely traverse the unordered part.
D) O(n^2) because we always have to completely traverse the unordered part.
