Assigned:
Wed 23 Sep 2009
Due:
Wed 30 Sep 2009
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: Do all four exercises (1 through 4) and two of the three problems (5, 6, 7).
Points: 15 pts per exercise and 20 points per problem.
Unless otherwise indicated, exercises and problems are from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The edition (2^{nd} or 3^{rd}) will be indicated if the numbering differs.
ThreeWaySort(A, i, j)
(a) Argue that ThreeWaySort(A, 1, n) correctly sorts the input array A[1 .. n].
(b) Give a recurrence for the worst-case running-time of ThreeWaySort and a tight asymptotic (Θ-notation) bound on the worst-case running time.
(c) Compare the worst-case running time of ThreeWaySort with that of insertion sort and mergesort.
(a) Given an array A[1 .. n] of n integers, show how a mode of A can be determined in O(n log n) time.
An array A[1 .. n] is said to have a majority element if more than half of its entries are the same. We would like to determine whether a given array A has a majority element, and if so, find the element. Unlike in part (a), however, we will not restrict the elements to be integers. In fact, we assume that the elements of the array are not necessarily from some ordered domain like the integers, so there can be no comparisons of the form "is A[i] > A[j]?''; only questions of the form "is A[i] = A[j]?" can be answered.
(b) Show how to solve the majority element problem in O(n log n) time.
Hint: Split the array into two arrays A_{1} and A_{2} of half the size. Use a divide-and-conquer approach that finds the majority element of A, if it exists, using the knowledge of majority elements of A_{1} and A_{2}, if they exist.)
(c) Can you give a linear-time algorithm?
Hint: Another divide-and-conquer approach is as follows:
(a) pair up the elements of A arbitrarily, to get n/2 pairs;
(b) if two elements of a pair are different, then discard both of them, else
keep just one of them. Show that after this procedure there are at
most n/2 elements left, and that they have a majority element if A does.