COMP 480/580 Probabilistic Algorithms and Data Structures

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 480/580 Probabilistic Algorithms and Data Structures

·  Instructor: Anshumali Shrivastava (anshumali AT rice)

·  TA and Office Hours:

·  Class Timings: Tue/Thu 02:30PM - 03:45PM

·  Location:KECK 100

·  Instructor Office Hours: Tuesday/Thurdsay 3:45 to 4:15 after class, DH 2083

Recent Announcement

List of sample project topics link

Please sign up for lectures you want to scribe at excel

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

·  Term Project or Final Exam: 30%

·  Assignments: 40%

·   Mid-Term Exam: 20%

·  Lecture Scribing:10%

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

·  08/22 : Brief Pseudo Randomness, Universal Hashing, Chaining, and Linear Probing. [Slide] ·  08/24 : Introduction, Logistics, Mark and Re-capture Estimation. [Scribe] [Slide]

·  08/29 : Markov, Chebyshev's, and C hernoff Bounds.

·  09/31 : Analysis of Hashing, Chaining and Probing.

·  09/05 : Compressed Cache and Bloom Filters. (Why caching does not kill your memory)

·  09/07 : Resizing Hash Tables: Consistent Hashing and balanced allocations.(The idea behind Akamai Technologies)

·  09/12 : Special Topic SPOCA: A Stateless, Proportional, Optimally-Consistent Addressing Algorithm. (Best paper in USENIX 2011)

·  09/14 : Introduction to Stream Computing and Reservoir Sampling. (Algorithms at the Edges) ·  09/19 : Stream Estimation 1: Count-Min Sketch (Generalized Bloom Filters)

·  09/21 : Stream Estimation 2: Count-Sketches

·  09/26 : Stream Estimation 3: Count Distinct and Norm Estimation on Streams.

·  09/28 : Minwise Hashing, Near-Duplicate Detection and LSH 1. (What is "hash function" in

this NY-Times article)

10/03 : Minwise Hashing, Near-Duplicate Detection and LSH 2.

10/05 : Reserve a SLOT for Spillover

10/10 : MIDTERM RECESS

10/12 : Basic Sampling. (Beyond Random Sampling)

10:17 : Basic Sampling 2

10/19 : More LSH (Eliminate Pairwise Comparisons)

10/24 : Advanced Sampling. LSH as Computationally Efficient Importance Samplers. (Adaptive Sampling at the Cost of Random Sampling)

10/26 : DNF Counting(A closer Look at Estimation via Sampling).

10/31 : In Class Mid-Term Exam.

11/02 : Markov Chains, Stationary distributions, MCMC 1 (Sampling in Complex Spaces). 11/07 : Markov Chains, Stationary distributions, MCMC 2.

11/09 : Markov Chains, Stationary distributions, MCMC 3.

11/14 : Markov Chains, Stationary distributions, MCMC 4.

11/23 : THANKSGIVING RECESS

11/28 : Special Topics

11/30 : 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 / [email protected] / x5841) to determine the accommodations you need; and 2) meet with me to discuss your accommodation needs.


2023-08-26