A randomized algorithm for sorting.

1. pick a pivot
2. partition the array into bigger and less than the pivot (see k-select)
3. recurse on L, R
4. return concatenated L, pivot, R

additional information

stability

quicksort is not stable (it doesn’t preserve equal elements’ order).

recurrence relationship

\begin{equation} T\qty(n) = T\qty(|L|) + T\qty(|R|) + O\qty(n) \end{equation}

recurse on left, recurse on right, the partitioning. In an idea world, suppose the array is split exactly in half, then:

randomized algorithm is a type of algorithm, similar to relaxation.

• Make a hard problem easier by changing the problem
• What if, instead of guaranteeing we find the best/correct answer, we only provide some chance of finding the best/correct answer?

Las Vegas algorithms

see Las Vegas algorithm

best and average case randomness

Two notions of randomized algorithm runtime: expected running time (you pick randomness, what’s the worst case input running time) vs worst-case running time (adversary picks randomness, what’s the worst case running time?).

Key Sequence

Notation

New Concepts

• randomized algorithm
  • Las Vegas algorithm
  • best and average case randomness
• bogo sort
• quicksort

Important Results / Claims

Questions

Interesting Factoids

Three models of fitting. Consider trying to fit some dataset \(|D|= n\) that’s roughly quadratic with…

• a linear model: underfit, high bias (i.e. “model imposes bias of linearity on data”)
• a nth order polynomial: overfit, high variance (i.e. “a small perturbation of data brings lots of change”)

Its important to pay attention if you are having high bias of high variance—solutions of each is different from each other.

intuition of overfitting

See overfit