This is the archived website of SI 486H from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Classes

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: Discrete Math (Classes 1–4)
    Introduction, Probability basics, Expected analysis
  • Unit 2: Architecture (Classes 5–8)
    Information and entropy, Random numbers, Hardware, PRNGs (software)
  • Unit 3: Data structures (Classes 9–18)
    Skip lists, Treaps, Random BSTs, Hash functions, Bloom filters, Perfect Hashing
  • Unit 4: Computer Security (Classes 19–23)
    Secure RNGs, Randomized encryption, Oblivious Transfer, Garbled Circuits, ORAMs
  • Unit 5: Algorithms (Classes 24–29)
    Game tree evaluation, Minimum spanning trees, Identity testing, Fingerprinting