Description
Problem 1: Quicksort (8+5+2=15 points)
- 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 (6+4=10 points))
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. (4 points)
Show that lgn! = Θ(nlgn) without using Stirling’s formula.
