\documentclass[12pt]{article} \usepackage{amsmath} $\newcommand{\indx}{{\it index}}$ \parindent0pt

Intro

Administrivia.

Randomized algorithms: make random choices during run. Main benefits:

Distinguish average-cast analysis

We don't really use random numbers. But randomized algorithms break patterns we don't know are there.

Course objective:

Basic methodologies.

Today: 2 really basic principles:

Then some fundamental ideas:

Quicksort

Items $S_1,\ldots,S_n$ to be sorted

BSP

MinCut

Consequence: counting number of min-cuts.

Consequence: enumerating all min-cuts.

Min-cut implementation

Monte Carlo vs. Las Vegas