Frances' Notes for Friday, September 17th, 2004

• == Scales of Justice ==
  • Problem: Given 9 balls and a pan scale, how many weighs are necessary to find the heavy ball. Answer: Two. Divide the balls into three groups and place one group in each pan and one on the table. The theoretical bounds of searching are only true if you don't do tricks. How can you search if allthe balls have different weights.
  == Searching ==
  1. Find the Min/Max Simultaneously - Compare two, then compare the higher one to the current max and the lesser one to the current min. O = (3/2)n
  2. Definition: Order - a function is That random pivot could be really good, or really bad. It depends ont eh pivot. We're going to take the whole set of things and divide it into five. Next, we find the median of each of these five. Compare the median of the medians.
  3. Split into n/5 groups of 5 = O(n)
  4. find median of each - n/5 * 6
  5. find the median of medians