Mini #2, 15451 Spring 2005
==========================
This mini is due via *email*, by 11:59pm Tue, Feb. 7th. PLEASE NOTE:
all students (of both sections) should email their answers for this
mini to Daniel Golovin . When submitting,
please use the subject line "15-451 MINI #2" in your email. If you
have a question, please use the subject line "15-451 MINI #2 QUESTION"
in your email.
1. Recall the deterministic linear-time algorithm for
finding the median (or kth smallest element) of an unsorted array,
which can be found in the notes, chapter 4.
Our analysis of this algorithm gave the recurrence:
T(n) <= T(n/5) + T(7n/10) + cn.
Suppose we changed the algorithm so that rather than breaking up the
array into groups of size 5, we used groups of size 7 instead.
(a) What is the recurrence that results?
(b) What does this solve to?
2. Sorting.
(a) Show that it is possible to sort any array of 4 elements using
only 5 comparisons. Note: there are multiple correct ways to do this.
(b) Is it possible to sort every array of size 4 using only 4
comparisons? Why or why not?
3. Binary Search Trees.
(a) In addition to Find, Insert and Delete, suppose that
we also want to support the following operation:
Key_at_position(k) Return the key that's stored
in the kth position (they are
numbered 1, 2, 3....n) in a
binary search tree, in symmetric
(left ---> right) order.
What additional field(s) would you have to keep in the tree to
accommodate this operation efficiently? Briefly explain the
algorithm for this operation using the field(s) you propose.
(b) Suppose that we wanted to efficiently support the following
operation:
Sum_Range(i,j) Return the sum of the keys that are in
positions i....j. Where "position" is defined as
in part (a).
What additional fields (over what you used in part a) would be
required to do this efficiently? Briefly explain the algorithm
for this operation using the field(s) you propose.
By "efficient" in this problem we mean O(log n).