1) a)Consider the following modication to binary search: instead of picking the
ID: 3862005 • Letter: 1
Question
1) a)Consider the following modication to binary search: instead of picking the middle element for comparison, pick any element (uniformly at random). (a) Give pseudocode for this randomized binary search algorithm. (b) What is the expected running time of this algorithm? Prove it.
b) Consider a modied Merge Sort algorithm, in which a given sequence is split into three sub-sequences of equal size approximately one-third. Write down the recurrence equation for this modied Merge Sort algorithm and nd the asymptotic complexity of this algorithm.
Explanation / Answer
1.a
a) The purpose of the algorithm is to select the ith smallest element in a set with some underlying order. Recall that in this algorithm, we first picked an an element p in the middle half of the set, that is, one whose value was simultaneously larger than at least 1/4 of the items and smaller than at least 1/4 of the items.
We used p to partition the items into two sets and then recursed on one of the two sets. If you recall, we worked very hard to find an item in the middle half, so that our partitioning would work well.
It is natural to try instead to just pick a partition element at random, because, with probability 1/2, this element will be in the middle half.
Algorithm:
RandomSelect(A,i,n)
(selects the ith smallest element in set A, where n = |A| )
if (n = 1)
return the one item in A
else
p = randomElement(A)
Let H be the set of elements greater than p
Let L be the set of elements less than or equal to p
If H is empty
put p in H
if (i |L|)
Return RandomSelect(L, i, |L|)
else
Return RandomSelect(H,i |L|, |H|)
Here randomElement(A) returns one element from A uniformly at random. We use this element as our partition element; that is, we use it to divide A into sets L and H with every element less than the partition element in L and every element greater than it in H.
We add the special case when H is empty, to ensure that both recursive problems have size strictly less than n. This simplifies a detailed analysis, but is not strictly necessary.
At the end of this section we will show how to get a recurrence that describes fairly precisely the time needed to carry out this algorithm. However, by being a bit less precise, we can still get the same big-O upper bound with less work.
When we choose our partition element, half the time it will be between 1 4n and 3 4n. Then when we partition our set into H and L, each of these sets will have no more than 3 4n elements. The other half of the time each of H and L will have no more than n elements. In any case, the time to partition our set into H and L is O(n). Thus we may write
T(n) 1 2T( 3 4n) + 1 2T(n) + bn if n > 1
if n = 1.
We may rewrite the recursive part of the recurrence as
2 T(n) 1 2 T 3 4 n + bn,
T(n) T 3 4 n + 2bn = T 3 4 n + b n.
each time our algorithm chooses a pivot element, it chooses the worst one possible, in which case the selection process could take n rounds, and thus take time (n2). Why, then, is it of interest? If involves far less computation than finding the median of medians, and its expected running time is still (n). Thus it is reasonable to suspect that on the average, it would be significantly faster than the deterministic process. In fact, with good implementations of both algorithms, this will be the case.
b)
the expected running time of this algorithm:
Runtime
Worst-case O(n 2 )
Best-case O(n 2 )
Expected-case O(n 2 )
We pick a random element, and then use it to partition the set of items into two sets L and H. In this case, we don’t recurse on one or the other, but recurse on both, sorting each one. After both L and H have been sorted, we just concatenate them to get a sorted list.
Here is a pseudocode description of quicksort
Quicksort(A,n)
if (n = 1)
return the one item in A
else
p = randomElement(A)
Let H be the set of elements greater than p;
Let h = |H| Let L be the set of elements less than or equal to p;
Let = |L| If H is empty
put p in H
A1 = QuickSort(H,h)
A2 = QuickSort(L,)
return the concatenation of A1 and A2.
Quicksort(A,n) if (n = 1) return the one item in A else p = randomElement(A) Let H be the set of elements greater than p; Let h = |H| Let L be the set of elements less than or equal to p; Let = |L| If H is empty put p in H A1 = QuickSort(H,h) A2 = QuickSort(L,) return the concatenation of A1 and A2.
T(n) = 2T(n/2) + O(n) if n > 1
O(1) if n = 1
and we know by the master theorem that all solutions to this recurrence have T(n) = O(n log n).
Then if T(n) is the expected running time for a list of length n, then for some constant b
T(n) E(r)bn + T(ann) + T((1 an)n).
b.
MergeSort:
The example of a divide-and-conquer algorithm which we will consider is perhaps the best known. This is a simple and very efficient algorithm for sorting a list of numbers, called MergeSort.
We are given an sequence of n numbers A, which we will assume is stored in an array A[1 ...n]. The objective is to output a permutation of this sequence, sorted in increasing order.
This is normally done by permuting the elements within the array A. How can we apply divide-and-conquer to sorting? Here are the major elements of the MergeSort algorithm.
Divide: Split A down the middle into two subsequences, each of size roughly n/2.
Conquer: Sort each subsequence (by calling MergeSort recursively on each).
Combine: Merge the two sorted subsequences into a single sorted list.
The dividing process ends when we have split the subsequences down to a single item.
An sequence of length one is trivially sorted.
The key operation where all the work is done is in the combine stage, which merges together two sorted lists into a single sorted list.
It turns out that the merging process is quite easy to implement.
The following figure gives a high-level view of the algorithm. The “divide” phase is shown on the left. It works top-down splitting up the list into smaller sublists. The “conquerand combine” phases are shown on the right. They work bottom-up, merging sorted lists together into larger sorted lists.
MergeSort(array A, int p, int r)
{
if (p < r)
{ // we have at least 2 items
q = (p + r)/2
MergeSort(A, p, q) // sort A[p..q]
MergeSort(A, q+1, r) // sort A[q+1..r]
Merge(A, p, q, r) // merge everything together
}
}
Merging:
All that is left is to describe the procedure that merges two sorted lists. Merge(A, p, q, r) assumes that the left subarray, A[p..q], and the right subarray, A[q + 1..r], have already been sorted. We merge these two subarrays by copying the elements to a temporary working array called B. For convenience, we will assume that the array B has the same index range A, that is, B[p..r]. (One nice thing about pseudocode, is that we can make these assumptions, and leave them up to the programmer to figure out how to implement it.) We have to indices i and j, that point to the current elements of each subarray. We move the smaller element into the next position of B (indicated by index k) and then increment the corresponding index (either i or j). When we run out of elements in one array, then we just copy the rest of the other array into B. Finally, we copy the entire contents of B back into A. (The use of the temporary array is a bit unpleasant, but this is impossible to overcome entirely. It is one of the shortcomings of MergeSort, compared to some of the other efficient sorting algorithms.) In case you are not aware of C notation, the operator i++ returns the current value of i, and then increments this variable by one.
Merge(array A, int p, int q, int r) { // merges A[p..q] with A[q+1..r]
array B[p..r] i = k = p // initialize pointers
j = q+1
while (i <= q and j <= r)
{ // while both subarrays are nonempty
if (A[i] <= A[j])
B[k++] = A[i++] // copy from left subarray
else B[k++] = A[j++] // copy from right subarray
}
while (i <= q)
B[k++] = A[i++] // copy any leftover to B
while (j <= r)
B[k++] = A[j++]
for i = p to r do A[i] = B[i] // copy B back to A
}
}
Divide and Conquer and Recurrences:
Last time we introduced divide-and-conquer as a basic technique for designing efficient algorithms. Recall that the basic steps in divide-and-conquer solution are
(1) divide the problem into a small number of subproblems,
(2) solve each subproblem recursively, and
(3) combine the solutions to the subproblems to a global solution. We also described MergeSort, a sorting algorithm based on divide-and-conquer. Because divide-and-conquer is an important design technique, and because it naturally gives rise to recursive algorithms, it is important to develop mathematical techniques for solving recurrences, either exactly or asymptotically. To do this, we introduced the notion of a recurrence, that is, a recursively defined function.
MergeSort Recurrence:
Here is the recurrence we derived last time for MergeSort. Recall that T(n) is the time to run MergeSort on a list of size n. We argued that if the list is of length 1, then the total sorting time is a constant (1). If n > 1, then we must recursively sort two sublists, one of size dn/2e and the other of size bn/2c, and the nonrecursive part took (n) time for splitting the list (constant time).
Runtime recurrence
T(n): time to sort array of size n T(1) = 1 T(n) = 2T(n/2) + O(n)
Asymptotic complexity:
O(n log n)
Much faster than O(n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.