1. In the proof of the comparison-based sorting lower bound, why do you need to have at least n! leaves, corresponding to the n! distinct permutations?

2. Problem 8.1-4 on page 168 of the 2nd edition, page 194 in 3rd edition.

3. Problem 9.3-8 on page 193 in the 2nd edition, page 223 in the 3rd edition.