CS 4102: Algorithms - University of Virginia School of Engineering and ...

[Pages:44]CS 4102: Algorithms

Lecture 8: Quickselect, Median of Medians

David Wu Fall 2019

Warm Up

Guess the solution to this recurrence:

7

= + +

5

10

where 1 is a constant

2

Warm Up

= /5 + 7/10 +

7 9 + = <

5 10 10

If this was /0 , then can

12

use Master's Theorem to conclude

Guess: Suffices to show since non-recursive cost is already

3

Warm Up

= /5 + 7/10 +

Claim: 10 Base Case: 0 = 0

1 = 1 10 which is true since 1

Strictly speaking, we can handle any > 0, but assuming 1 to simplify the analysis here

Warm Up

= /5 + 7/10 +

Inductive hypothesis: 2 : 10

Inductive step:

1

7

2 + 1 = 5 2 + 1 + 10 2 + 1

+ (2 + 1)

17

+ 5 10

10 2 + 1

+ (2 + 1)

= 9 2 + 1 + 2 + 1 = 10(2 + 1)

5

Today's Keywords

Divide and Conquer Sorting Quicksort Median Order Statistic Quickselect Median of Medians

CLRS Readings: Chapter 7

6

Homework

HW2 due today (September 19), 11pm ? Programming assignment (Python or Java) ? Divide and conquer (Closest pair of points)

HW3 released tonight ? Divide and conquer algorithms ? Written (use LaTeX!) ? Submit both zip and pdf!

7

Quickselect Algorithm

Algorithm to compute the th order statistic

? th smallest element in the list ? 1st order statistic: minimum ? th order statistic: maximum ? (/2)th order statistic: median

8

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download