Description

ALGORITHMS AND DATA STRUCTURES (CH08-320201)
Prof. Dr. Michael Sedlmair
Computer Science & Electrical Engineering
Problem 1: Quicksort (8+5+2=15 points)
(a) 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.
(b) Derive the best-case and worst-case running time for the modified Quicksort in (a).
(c) 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:
(a) Show by induction that

(b) 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.
Remarks