Course Description and Learning Objectives

In this course, we will see the power of randomness in algorithm design and analysis. Many problems have faster algorithms if randomization is allowed, and indeed, for certain problems randomness is essential. The learning objectives of the course are the following

Learn and master probabilistic tools which will help in design and analysis of algorithms.
Learn about applications of these ideas in areas such as big data/optimization/learning, etc.
Learn and master technical writing for communicating the design and analysis of above mentioned algorithms and applications.

Prerequisites

A first course on undergraduate algorithms (eg, COSC 31 @Dartmouth).
A basic course on probability (eg, probability module of COSC 30, or MATH 20/60 @Dartmouth).
"Mathematical maturity": the ability to read and write precise mathematical statements.

A Problem Set 0 to test your readiness (pdf)

Logistics

Class timing and venue: 10 hour (MWF, 10:10am - 11:15am), Cummings 200
Instruction Team and Office hours
- Deeparnab Chakrabarty, Instructor. Tuesdays, 4:30 - 5:30p, Thursdays, 12-1:30pm (X-hour) via Calendly, ECSC 110
- Hang Liao, Grad TA. OH: Mondays, 4:30-6pm at ECSC 106. (Out of town on Apr 17, OH moved to Apr 16, 5-6pm on Zoom)
- Ankita Sarkar, Grad TA. OH: Wednesdays 5-6p via Calendly, ECSC B010.
Work Submissions: Canvas, Gradescope
Announcements, Questions, Discussion: Ed Discussion
Policies: General policies; Honor Principle & COSC 34/234
Textbooks: No required textbook. Lecture notes are/will be posted.
Two recommended textbooks: "Randomized Algorithms" by R. Motwani & P. Raghavan; "Probability and Computing" by M. Mitzenmacher and E. Upfal. Dartmouth library gives free online access to the first book. I also prefer that book to the latter, although that's just a personal preference.

Deliverables and Evaluation

(tl;dr)

Problem Sets (40%)
Middle of the term test (20%)
Etc (40%)

details

Tentative Schedule

Date	Topic	Associated Problem	Other info
27th March	Introduction, Monte Carlo Algorithms, Equality	Problem 1, 2 (week1.pdf)
29th March	Las Vegas Algorithms, QuickSort	Problem 3, 4 (week1.pdf) Problem 5, (week2.pdf)
31st March	Karger's Minimum Cut Algorithm	Problem 5, 6 (week1.pdf)
3rd April	Estimation Algorithms, Chernoff Bounds	Problem 1, 2 (week2.pdf)
5th April	Median of Means Theorem, General Chernoff	Problem 2, 3, 5 (week2.pdf)
7th April	Randomized Median Algorithm	Problem 4 (week2.pdf)
10th April	Estimating #DNF : Importance Sampling	Problem 1 (week3.pdf)
12th April	Finding Similar Pairs via Importance Sampling	Problem 2 (week3.pdf)	How to sample?
14th April	Estimating the Average Degree in an Undirected Graph	Problem 3, 4 (week3.pdf)
17th April	Balls and Bins I: Birthday Paradox + Max Load	Problem 1, 2 (week4.pdf)
19th April	Balls and Bins II: Coupon Collection + Poisson RVs
21st April	Balls and Bins III: Poissonization + Applications	Problem 3,4 (week4.pdf)
24th April	Hashing I: Universal Hash Families	Problem 3 (week5.pdf)
26th April	Hashing II: Fingerprinting	Problem 1,2 (week5.pdf)
28th April	Hashing III: Perfect Hashing	Problem 4 (week5.pdf)
1st May	Locality Sensitive Hashing (LSH) and Nearest Nbrs	Problem 1, 2 (week6.pdf)	See this retrospective talk by Moses Charkar.
3rd May	Locality Sensitive Hashing (LSH) and Nearest Nbrs
5th May	LSH Families	Problem 3, 4 (week6.pdf)
May (5th - 7th)	Release: May 5th (~ noon), due May 7th (~ midnight)		Take Home Midterm
8th May	Streaming I: Frequency estimation + Count-Min Sketch	Problem 1 (week7.pdf)
10th May	Streaming II: Count-Sketch + F2 estimation	Problem 2 (week7.pdf)
12th May	Streaming III: Counting Distinct Elements	Problem 3,4 (week7.pdf)
15th May	Cancelled due to gravity and (lack of sufficient) friction
17th May	Online Learning I: The Experts Problem
19th May	Online Learning II: Randomized Majority & MWU		An excellent survey
22nd May	Online Learning III: Follow the Perturbed Leader
24th May	Dimension Reduction: Johnson-Lindenstrauss
26th May	A Lecture on Derandomization	Thank you Matthew Ellison for scribing!
31st May	Conclusion: what was this course about + AMA