COMP 480/580 Probabilistic Algorithms and Data Structures
- Instructor: Anshumali Shrivastava (anshumali AT rice)
- TA: Constantinos Chamzas , Mohammadamin Edrisi , Zhen Cao , Ryan Spring
- TA Office Hours: 10 am Thur (Ryan Spring in DH 3035), Mon 4pm and Wed 4pm (DH 3110)
- Class Timings: Tue/Thu 01:00PM - 02:15PM
- Location: RYN 201
- Instructor Office Hours: Tue 2:15PM - 3:15PM DH 3118 (Anshu)
Recent Announcement
Assignment 4 released pdf
Assignment 3 released pdf
Assignment 2 released pdf
Assignment 1 released pdf
List of sample project topics link
Please select a lecture to scribe by putting your name in the link
Overview
This course will be ideal for someone wanting to build a strong foundation in the theory and practice of algorithms for
processing Big-Data. We will discuss advanced data structures and algorithms going beyond deterministic setting and emphasize the role
of randomness in getting significant, often exponential, improvements in computations and memory.
Grading
Prerequisite
COMP 182 or equivalent required. COMP 382 is useful but not required. Basic Knowledge of
Probability. Knowledge of programming is required. Capability to manipulate primitive data structures such as arrays, list, etc. will
be needed for assignments.
Materials
Most of the materials (scribes and slides) needed will be posted on this website.
Some of the materials are fairly new and textbook is yet to be written.
A Nice Book to have is "Probability and Computing: Randomized Algorithms and Probabilistic Analysis
" by Michael Mitzenmacher and Eli Upfal.
Schedule
- 01/08 : Introduction, Logistics, Mark and Re-capture Estimation.Scribe Slide
- 01/10 : Brief Pseudo Randomness, Universal Hashing, Chaining, and Linear Probing. Slide
- 01/15 : Markov, Chebyshev's, and Chernoff Bounds. (Guest Lecture by Luay) Slide Scribe
- 01/17 : Analysis of Hashing, Chaining and Probing.Slide Scribe
- 01/22 : Compressed Cache and Bloom Filters. Slide Scribe (Why caching does not kill your memory)
- 01/24 : Resizing Hash Tables: Consistent Hashing and balanced allocations. Slide Scribe (The idea behind Akamai Technologies)
- 01/29 : SPOCA: A Stateless, Proportional, Optimally-Consistent Addressing Algorithm. Slide Scribe (Best paper in USENIX 2011)
- 01/31 : Introduction to Stream Computing and Reservoir Sampling. Slide Scribe (Algorithms at the Edges)
- 02/05 : Stream Estimation 1: Count-Min Sketch (Generalized Bloom Filters)Slide Scribe .
- 02/07 : Spring Break.
- 02/12 : Stream Estimation 2: Count-Sketches BlackboardSnapshot Scribe
- 02/14 : TBD
- 02/19 : Minwise Hashing, Near-Duplicate Detection and LSH 1. Slides Scribe (What is "hash function" in this NY-Times article)
- 02/21 : Minwise Hashing, Near-Duplicate Detection and LSH 2.Slides Scribe
- 02/26 : More LSH Slides (Eliminate Pairwise Comparisons)
- 02/28 : Basic Sampling. Slides Scribe (Beyond Random Sampling)
- 03/05 : Sampling Continued Slides Scribe
- 03/07 : LSH as Computationally Efficient Importance Samplers. Slides Scribe (Adaptive Sampling at the Cost of Random Sampling)
- 03/12 : Spring Break.
- 03/14 : Spring Break.
- 03/19 : In Class Mid-Term Exam.
- 03/21 : Markov Chains, Stationary distributions, MCMC 1 Scribe (Sampling in Complex Spaces).
- 03/26 : Markov Chains, Stationary distributions, MCMC 2 Scribe
- 03/28 : Markov Chains, Stationary distributions, MCMC 3 Scribe
- 04/02 : Markov Chains, Stationary distributions, MCMC 4.
- 04/04 : Markov Chains, Stationary distributions, MCMC 5. Scribe
- 04/09 : Randomized Routing. Scribe
- 04/11 : Probabilistic Method. (Proving Existence)
- 04/16 : Compressed Sensing 2.
- 04/18 : Slack or Special Topics
Students with Disability
If you have a documented disability that may affect academic performance, you should: 1) make sure this documentation is on file with Disability Support Services (Allen Center, Room 111 / adarice@rice.edu / x5841) to determine the accommodations you need; and 2) meet with me to discuss your accommodation needs.