1. Simultaneous Max and Min

   (a) Create an Divide-and-Conquer comparison-based algorithm that, given a set of N numbers, finds both a maximum and minimum element of the set, and derive the worst-case number of comparisons required. The complexity of your algorithm should be better than 2N-c comparisons (for any constant c). [Note: this is a somewhat artificial problem, since it's not hard to find such an algorithm without using D&C. However, I'd like you to use D&C anyway, since that's the purpose of the exercise.]

   (b) Prove a lower bound (which should be greater than N+c, for any constant c) on the number of comparisons reqired to find the Max and Min of a set. [Note - this can be a "rest-of-the-course" style proof.] Ideally, your lower bound should match your algorithm's complexity, at least for the case that N is a power of 2.

2. A Formal Proof

   Prove formally and carefully that if f(n) is O(n^3) and g(n) is O(2^n), then f(n)+g(n) is O(2^n).

There are two parts to the homework that may be difficult ...

- Figuring out how to compare an exponential function to a polynomial one. Here's two possible ways: (1) Use calculus. (2) Pick n_0 and c so huge that it's really easy to make the comparison.

- I didn't do a good job of explaining what I was looking for in part 1(b). I'm asking you to do something very difficult, and I will be very pleased if anyone does a good job on it. Namely, I'm asking you to show that for any algorithm that only uses two-way comparisons to find out about the data, and for any constant c, there must be some input instance of size n for which the algorithm makes more than n+c comparisons.
One reason that this might be hard is that I haven't given you any "machinery" to prove things about "all algorithms". So let me give a hand-waving proof that any algorithm that correctly finds the maximum of n distinct elements must use at least n-1 comparisons.
Proof: Suppose A is an algorithm that uses at most n-2 comparisons. Then there will be at most n-2 elements that turned out to be the "loser" of a comparison (i.e., they were smaller value being compared). Thus, there are at least 2 elements that were not losers. It's obvious that either of these element might be the maximum. [If you challenge me to explain why that's obvious, I'll mumble something about how I can construct two instances to the problem that run identically, but have different maximums.] Thus, it's impossible that the algorithms correctly identifies which the maximum is (unless it gets lucky, but that won't always happen).
Assuming you believe this, I've shown that if an algorithm uses at most n-2 comparisons, it can't identify the maximum. Thus, if it correctly finds the maximum, it must use at least n-1 comparisons.