• 6.5210/18.415: Advanced Algorithms
  • PSets
  • Calendar
  • Materials
  • Information
  • Hashing

    David Karger

    Everything you need to know about probability

    Hashing

    Dictionaries

    Model

    Hashing:

    Hash families:

    Set of all functions?

    How about a random function?

    Problem:

    2-universal family: [Carter-Wegman]

    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

    Define las vegas, compare to monte carlo.

    Derandomization

    Followups