Exercises
- Exercises 4.1, 4.2, 4.3, 4.15, 4.16.
- Show that RANDOMPERMUTATION generates all permutations with the same probability.
- Show that it must take at least the order of n log n to compute the intersection of n halfplanes (some model assumptions are required to make this formal, but take that lightly). Hint: reduce from sorting.