Problem 1: Quicksort
- Implement a modified version of the Quicksort algorithm, where the sequence is always split into three subsequences by simultaneously using the first two elements as pivots.
- Derive the best-case and worst-case running time for the modified Quicksort in (a).
- Implement a modified version of the Randomized Quicksort algorithm, where the sequence is always split into three subsequences by simultaneously using two random elements as pivots.
Problem 2: Randomized Quicksort
To formally complete the proof of the expected time complexity E[T(n)] for the Randomized Quicksort algorithm when applied to an input sequence of length n, provide the following steps:
- Show by induction that
- Show by induction that
E[T(n)] ≥cnlgn
for a constant c> 0.
Problem 3: Decision Trees.
Show that lgn! = Θ(nlgn) without using Stirling’s formula.
