CS 215 Homework 6

1. There are n! possible permutations of n items. Chapter 7 makes use of this fact to prove that any sorting algorithm that sorts on the basis of comparison of keys requires Ω(nlgn) comparisons. Assume that we know that only 2ⁿ of those permutations are actually possible. Use the same style of argument as is provided in Chapter 7 to determine a lower bound on the number of comparisons required for this new, easier, class of sorting problems.
2. Chapter 8, question 14.
3. (Optional, Extra credit) Chapter 8, question 21.