\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt
This material takes 1:05.

Everything you need to know about probability

Hashing

Dictionaries

Model

Hashing:

Hash families:

2013 lecture 7 start

Set of all functions?

How about a random function?

Problem:

2-universal family: [Carter-Wegman]

2012 lecture start

perfect hash families

Fredman Komlos Szemeredi.

Ideally, would hash with no collisions

Alternative try: use more space:

Finding one

Two level hashing for linear space

2013 Lecture 7 End

Define las vegas, compare to monte carlo.

Derandomization

Followups