Warning: The hard deadline has passed. You can attempt it, but you will not get credit for it. You are welcome to try it as a learning exercise.
To specify an array or sequence of values in an answer, separate the values inthe sequence by whitespace. For example, if the question asks for the firstten powers of two (starting at 1), then the following answer is acceptable: 1 2 4 8 16 32 64 128 256 512If you wish to discuss a particular question and answer in the forums, pleasepost the entire question and answer, including the seed (which can be used bythe course staff to uniquely identify the question) and the explanation (whichcontains the correct answer).
(seed = 680749)Give the array that results after applying the standard 2-way partitioningsubroutine from lecture to the following array: 61 13 37 73 97 44 72 56 85 29 10 57 Your answer should be a sequence of 12 integers, separated by whitespace.Recall, in the standard 2-way partitioning subroutine, the leftmost entry is the partitioning item.
(seed = 918325)Give the array that results after applying Dijkstra's 3-way partitioningsubroutine from lecture to the following array: 52 52 52 52 59 86 46 10 90 49 Your answer should be a sequence of 10 integers, separated by whitespace.
(seed = 378091)Which of the following statements about quicksort are true? Check all that apply. Unless otherwise specified, assume that quicksort refers to the recursive, randomized version of quicksort (with no extra optimizations) and uses the 2-way partitioning algorithm described in lecture.
The maximum number of recursive function calls to sort() when quicksorting an array of N distinct items is no more than 2N.
The expected number of compares to quicksort a uniformly random array of N distinct keys is asymptotically less than the number of compares to mergesort the same array.
The main reason for stopping the scan on equal keys in quicksort partitioning is to avoid quadratic performance for inputs with only one (or a few) distinct keys.
When partitioning a subarray of L keys (all of which are distinct), during quicksort, the probability that the key in the partitioning item is the ith smallest is 1 / L for each valid value of i.
The number of compares to quicksort an array of N items with only two distinct keys is linear.