Randomized Algorithms-ALL SECTIONS (SP21)

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. 

Course Goals

  • Understand how randomness can help in computation.
  • Learn and master probabilistic tools which will help in design and analysis of algorithms.
  • Applications in areas such as big data/optimization/learning, etc.
  • Technical Writing 

Schedule

29th March Lecture 1 : Introduction, Equality, Monte-Carlo
31st March Lecture 2 : Linearity of Expectation, QuickSort, Las Vegas
2nd April Lecture 3 : Karger's Minimum Cut Algorithm
5th April Lecture 4 : Estimation Algorithms, Chernoff Bounds 
7th April Lecture 5 : Median of Means Theorem, General Chernoff 
9th April Lecture 6 : Randomized Median Algorithm 
12th April Lecture 7 : Estimating #DNF solutions via Importance Sampling 
14th April Lecture 8 : Finding Similar Pairs via Importance Sampling 
16th April Lecture 9 : Estimating the Average Degree in an Undirected Graph 
19th April Lecture 10 : Balls and Bins, Birthday Paradox, Max Load 
21st April Lecture 11 : Balls and Bins, Coupon Collector, Poisson Random Variables 
23rd April Lecture 12 : Balls and Bins, Poisson Approximation + Applications 
26th April Lecture 13 : Hashing, Dictionary Maintenance, Universal Hash Families 
28th April Lecture 14 : Fingerprinting 
30th April Lecture 15 : Perfect Hashing 
3rd May Lecture 16 : Streaming I : Count-Min 
5th May Lecture 17 : Streaming II : Count-Sketch, Estimating F2 
7th May Lecture 18 : Streaming III : Reservoir Sampling, Estimating F_k 
10th May Lecture 19 : Streaming IV : Distinct Elements, Flajolet-Martin 
12th May Lecture 20 : Streaming V : More on Distinct Items, BJKST 
14th May Lecture 21 : Streaming VI : Distinct Elements with Deletion 
17th May Lecture 22 : The Experts Problem 
19th May Lecture 23 : Randomized Majority 
21st May Lecture 24 : Follow the Perturbed Leader 
24th May Lecture 25 : Randomization and Approximation Algorithms 
26th May Lecture 26 + 27 : k-means++ 
28th May Lecture 26 + 27 : k-means++ 
2nd June Lecture 28 : Wrap-up, AMA 

Pre-Requisites

Mathematical Maturity. A course in undergraduate algorithms and familiarity with discrete probability. For Dartmouth UGs: CS 30 and CS 31. Regardless, you have to do this Are you ready? quiz by April 1 (10 questions, and you can do it right now!)

Logistics

Instructor: Deeparnab Chakrabarty (DeepC)
TA: Maryam Negahbani

Class will be held remotely and synchronously in the E-slot (MWF, 1:10p - 2:15p)
See "Announcements" for links

Remote Classroom Expectation

I expect everyone to attend every lecture with their videos on and mics muted. This should be the default. If needed, please use a virtual background. I take a LOT of visual cues from student faces, and keeping the video on helps.

Textbook

There is no required textbook. But the following book is just awesome! 
"Randomized Algorithms" by R. Motwani and P. Raghavan.

Office Hours

See "Announcements" for links

Notification to Students

(1) Consent to recording of course meetings and office hours that are open to multiple students.

By enrolling in this course,

a) I affirm my understanding that the instructor may record meetings of this course and any associated meetings open to multiple students and the instructor, including but not limited to scheduled and ad hoc office hours and other consultations, within any digital platform, including those used to offer remote instruction for this course.

b) I further affirm that the instructor owns the copyright to their instructional materials, of which these recordings constitute a part, and my distribution of any of these recordings in whole or in part to any person or entity other than other members of the class without prior written consent of the instructor may be subject to discipline by Dartmouth up to and including separation from Dartmouth.

(2) Requirement of consent to one-on-one recordings

By enrolling in this course, I hereby affirm that I will not make a recording in any medium of any one-on-one meeting with the instructor or another member of the class or group of members of the class without obtaining the prior written consent of all those participating, and I understand that if I violate this prohibition, I will be subject to discipline by Dartmouth up to and including separation from Dartmouth, as well as any other civil or criminal penalties under applicable law. I understand that an exception to this consent applies to accommodations approved by SAS for a student’s disability, and that one or more students in a class may record class lectures, discussions, lab sessions, and review sessions and take pictures of essential information, and/or be provided class notes for personal study use only.


If you have questions, please contact the Office of the Dean of the Faculty of Arts and Sciences.

Accessibility Needs

Let me know before the end of the second week of the term if you will need a disability-related accommodation or service. In order for accommodations to be authorized, students are required to consult with Student Accessibility Services ("SAS" <student.accessibility.services@dartmouth.edu>; SAS websiteLinks to an external site.; phone: 603-646-9900) and to email me their SAS accommodation form. We will then work together with SAS if accommodations need to be modified based on the online learning environment. If students have questions about whether they are eligible for accommodations, they should contact the SAS office. All inquiries and discussions will remain confidential.

Wellness

We recognize that the academic environment at Dartmouth is challenging, that our terms are intensive, and that classes are not the only demanding part of your life. There are a number of resources available to you on campus to support your wellness, including: your undergraduate deanLinks to an external site., Counseling and Human DevelopmentLinks to an external site., and the Student Wellness CenterLinks to an external site.. I encourage you to use these resources and come speak with me to take care of yourself throughout the term.

COVID-19 addendum

While the COVID-19 pandemic has already changed how this course is structured, it has the potential to result in further personal impact which may prevent you from continuing engagement in the class. This may be due to contraction of the disease by you or a loved one, increased familial responsibilities, financial difficulties, or impacts on your mental/emotional health.

I have structured the course so that, hopefully, these disruptions will not prevent you from successfully learning the material.

In the event that you are directly or indirectly impacted by COVID-19 in such a way that will affect your performance in the course, it is imperative that you reach out to me as soon as possible. You may also reach out to your undergraduate Dean if that would make you more comfortable. We cannot assist you if we don’t know there is a problem. Our first priority is your health and security. We will work to put you in touch with appropriate resources to assist you.

Religious Observances 

Students may wish to participate in religious observances during the academic term. Please include this language on your Canvas site:

Some students may wish to take part in religious observances that occur during this academic term. If you have a religious observance that conflicts with your participation in the course, please meet with me before the end of the second week of the term to discuss appropriate accommodations. 

To assist with calendar planning and awareness of our diverse religious and spiritual community, the list of holy days for 2020/2021 can be found at https://students.dartmouth.edu/tucker/spiritual-life/about-spiritual-life/holy-day-calendar. The list represents major holy days which may impact accommodation of campus events in general, as well as student course attendance, exams, Commencement and participation in activities 2020-2021.  Thank you for your consideration.   If you have any questions about these dates or other concerns, please contact Rabbi Daveen Litwin, Dean and Chaplain of the Tucker Center for Spiritual and Ethical Life.