Description
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
nX−1
k=2
k lg k ≤
1
2
n
2
lg n −
1
8
n
2
(b) Show by induction that
E[T(n)] ≥ cn lg n
for a constant c > 0.
Problem 3: Decision Trees. (4 points)
Show that lg n! = Θ(n lg n) without using Stirling’s formula.
Remarks
Solutions have to be handed in via Moodle by the due date. For late submissions you need to get in contact
with the TAs directly. You need to upload one zip-file that contains a PDF-file for the theoretical parts and
source files (no executables or object files) for the programming assignments. The source files need to
include a makefile. Programming assignments need to be handed in as C, C++, or Python code. Please
write your own code. It is ok to take snippets from online resources, but they need to be clearly marked.