EECS 4101/5101: Advanced Data Structures

Fall 2023

Basic Information

Instructor: Aditya Potukuchi

Time: MW 08:30-1000 CC 108

Office Hours: M 11:00-12:00 LAS3052B or by appointment

Basic info handout

Probability practice problems

Quiz 1 solutions

Problem set 1

Schedule

Sep 06: Administrivia, probability recap ; reading: CLRS Appendix C.2

Sep 11: Random variables recap, intro to hashing; reading: CLRS Appendix C.3

Sep 13: Probability practice problems

Sep 18: Intro to hashing; reading: CLRS Chapters 11.1, 11.2

Sep 20: Quiz

Sep 25: Hashing contd; reading: CLRS Chapters 11.2, 11.3

Sep 27: Intro to multiplicative hashing; reading: CLRS Chapter 11.3.3

Oct 2: Analysis of multiplicative hashing, Intro to Bloom filters; reading: CLRS Chapter 11.3.3

Oct 4: Review, practice problems

Oct 9: NO CLASS, READING WEEK

Oct 11:  NO CLASS, READING WEEK

Oct 16: Quiz 1

Oct 18: Intro to heavy hitters, CountMin Sketch

Oct 23: CountMin Sketch recap

Oct25: MIDTERM

Oct30: Variance and Chebyshev's inequality; reading  CLRS Appendix C.3

Nov1: Variance and Chebyshev's inequality, intro to Min Hash; reading  CLRS Appendix C.3

Nov6: MinHash

Nov 8: Recap of Heaps, Intro to Fibonacci heaps; reading: CLRS Chapter 20.