Consider the problem of finding the median of a three-element set {a, b, c} of orderable items.
a. What is the information-theoretic lower bound for comparison-based algorithms solving this problem?
b. Draw a decision tree for an algorithm solving this problem.
c. If the worst-case number of comparisons in your algorithm is greater than the information-theoretic lower bound, do you think an algorithm matching the lower bound exists? (Either find such an algorithm or prove its impossibility.)