• SI 486D
• Calendar
• Classes
• Problems
• Admin

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

The lectures are broken into 5 units, as shown below. The notes will be updated after every class. These pages are also reachable from the main calendar.

• Unit 1: Architecture (Classes 1–7)
  Introduction, Random numbers, Hardware, PRNGs (software)
• Unit 2: Data structures (Classes 8–13)
  Skip lists, Treaps, Random BSTs
• Unit 3: Algorithms (Classes 14–19)
  Game tree evaluation, Minimum spanning trees
• Unit 4: Hashing (Classes 20–24)
  Hash functions, Bloom filters, Perfect Hashing
• Unit 5: Verification (Classes 25–28)
  Indentity testing, Fingerprinting, Randomized complexity