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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- textmix using nlp and apis to generate chunked sentence eric
- exploring data using python 3 dr charles r severance
- project 1 reliable transport university of california berkeley
- split large files into smaller chunks monkeybread software
- cs 4102 algorithms university of virginia school of engineering and
- use python with r with reticulate cheat sheet github
- list processing in sml wellesley college
- performance of compressed inverted list caching in search engines
- cs4102 l8 quickselectmedianofmedians john r hott
- parallel computing in python using mpi4py yale university
Related searches
- university of scranton school code
- university of minnesota college of education
- university of minnesota school of social work
- university of wisconsin school rankings
- university of scranton school calendar
- university of minnesota school of education
- virginia department of banking and finance
- university of cincinnati school calendar
- university of cincinnati school schedule
- university of florida school ranking
- school of art and design
- high school of art and design nyc