1. Consider finding the median of three order-able elements A, B, and C: (a) Design an optimal algorithm to find the median. (b) Draw the possible posets after two comparisons. How do these posets show that your algorithm has optimal worst case cost? (c) Draw the decision tree for your algorithm and explain how the decision tree gives the worst case cost.

2. Consider determining if at least three of five integer values are non-zero using only operations of testing for equality to zero. Give an adversary strategy to force any algorithm to examine all of the five values. Explain why your adversary strategy works regardless of what comparison algorithm is used.

3. Use an adversary argument to prove a lower bound (an optimal worst case behavior) for any algorithm which determines if there are any duplicates in a sorted array of size n. In other words, how many comparisons can the adversary force any algorithm to perform and what strategy does the adversary use? (Remember that the adversarys answers must be consistent.)