## 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.