[SOLVED] CH08-320201-Homework 5: Algorithms And Data Structures

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.