Activity Sheet 17

Manager

name:

Recorder

name:

Speaker

name:

1. Consider the problem of finding the largest of four elements, A, B, C and D, where only comparisons between two elements are allowed.
   1. What is the information-theoretic lower bound for this problem? What height does it suggest for the corresponding decision tree?
   2. Construct the decision tree for an algorithm that solves this problem. Is it possible to do so while achieving the lower bound from the previous part?
   3. Describe an adversary model approach to this problem. What algorithm would the adversary follow? What lower bound does this adversary model suggest?