Announcements

  • Labs 1-5 and Tests 1-2 have been graded.

  • Final Project information is here. Please email me your group and proposed topic by 11:59pm April 9.

  • Current Week Notes

Course Info

Required Materials

  • Probability Textbook: We’ll mainly use a free online textbook for developing probability theory: A Computational Introduction to Number Theory and Applications, by Victor Shoup. Don’t be put off by the title — we’ll only use the chapter on discrete probability (Chapter 8). It is self-contained.

  • Required Textbook: Much of our computer science applications will come from Probability and Computing, by Mitzenmacher and Upfal.

  • Optional Textbook: Randomized Algorithms, by Motwani and Raghavan. This book is not required but is a good reference.

Course Overview, Goals, and Structure.

This course provides an introduction to algorithm design with a focus on randomized algorithms and data structures. Topics include analysis of algorithms, basics of discrete probability including tail inequalities, the probabilistic method, NP-Completeness, and applications to graph algorithms, streaming algorithms, communication complexity, and machine learning.

Prerequisites: CPSC 035 is required. Mathematics background at the level of Linear Algebra or higher is also required but may be taken concurrently.

Goals for the Course

  • You will know how to use discrete probability theory to describe and model randomized processes and algorithms.

  • You will be able to use discrete probability to analyze the performance of deterministic and randomized algorithms.

  • You will be able to design randomized algortihms that solve computational problems of moderate difficulty.

  • You will know several standard tail inequalities (Markov inequality, Chebyshev inequality, Chernoff bound) and be able to apply them to analyze perfomance of randomized algorithms.

  • You will be able to identify problems that are computationally intractable and argue why these problems might be hard to solve efficiently.

  • You will understand how to use probabilistic methods to understand structure and complexity of computational problems of moderate difficulty.

Above all, the goal of this course is to instill a deep understanding of discrete probability and the role randomness plays in computer science.

Class Structure

  • Class Meetings. Lecture material will cover course concepts in depth, include activities to practice concepts learned, and to facilitate student discussion.

  • Suggested Readings. There are no required readings for the class. However, there are suggested readings that reinforce lecture material and provide more context.

  • Gradescope Exercises. For the initial portion of the course where the focus is on discrete probability, we’ll use daily Gradescope exercises to reinforce new material. Each exercise will be released after lecture and be due at 11pm before the next lecture is due. My intent with these exercises is that they take approximately one hour of time, quickly reinforce material from class, and quickly identify any areas that require followup. Gradescope exercises will be graded on a check plus / check / check minus / did not complete scale.

  • Tests. There will be three 90 minute tests given throughout the semester, after roughly every four weeks. Tests will be closed book.

  • Lab Assignments. Each lab assignment will be partnered and come out roughly every two weeks.

  • Final Project. In lieu of a final exam, you and a partner will develop a final project that more deeply explores one area at the intersection of probability and computer science that is of greatest interest to you.

Schedule

WEEK DAY ANNOUNCEMENTS TOPIC & READINGS LAB ASSIGNMENTS
1

Jan 18

  

Course Introduction, Asymptotic Analysis

Week 1 Lab Exercises

Jan 20

  
2

Jan 23

  

Probability Definitions and Basics

  • Shoup 8.1

Lab Assignment 1

Jan 25

  

Jan 27

Drop/Add Ends
3

Jan 30

  

Conditional Probability, Independence

  • Shoup 8.2
  • Mitzenmacher & Upfal Ch 1

Week 3 Lab Exercises

Feb 01

  

Feb 03

  
 

Feb 06

Canceled Classes

Feb 08

Feb 10
4

Feb 13

  

Random Variables, Expectation

  • Shoup 8.3, 8.4
  • Mitzenmacher & Upfal Ch 2

Lab Assignment 2
hw2.tex

Feb 15

  

Feb 17

  
5

Feb 20

  

Moments and Deviations

  • Shoup 8.5
  • Mitzenmacher & Upfal Ch 3,4


Feb 22

Test 1 (Feb 23)

Feb 24

  
6

Feb 27

  

Randomized Algorithms

Lab Assignment 3

Mar 01

  

Mar 03

  
 

Mar 06

Spring Break

Mar 08

Mar 10
7

Mar 13

  

Randomized Data Structures

  • Mitzenmacher & Upfal Ch 5.1, 5.2, 5.5

Week 7 Lab Exercises

Mar 15

  

Mar 17

  
8

Mar 20

  

The Probabilistic Method

  • Mitzenmacher & Upfal Ch 6

3/20 lecture notes

3/20 lecture audio
3/22, 3/23 lecture notes

3/20 lecture audio

Lab Assignment 4

AMS paper

How To Read Research Papers

Mar 22

  

Mar 24

Travel -- no classes
9

Mar 27

Mar 29

Test 2 (Mar 30)

The Probabilistic Method

  • Mitzenmacher & Upfal Ch 6

(continued)

Lab Assignment 5

Mar 31

  
10

Apr 03

  

Random Graphs

  • Mitzenmacher & Upfal Ch 5.6, 6


Apr 05

  

Apr 07

  
11

Apr 10

  

Streaming Algorithms


Apr 12

  

Apr 14

  
12

Apr 17

  

Randomized Algorithms for AI


Apr 19

  

Apr 21

  
13

Apr 24

  

Intractability and NP-Completeness


Apr 26

Test 3 (Apr 27)

Apr 28

  

Grading

Grades will be weighted as follows:

Gradescope Exercises

15%

Lab Assignments

15%

Test 1, in lab 2/16/23

15%

Test 2, in lab 3/23/23

15%

Test 3, in lab 4/20/23

15%

Final Project

20%

Class Participation

5%

Policies

Class Attendance

You should attend every class. If you need to miss a class or circumstances arise that make it difficult or impossible to attend, please let me know as soon as possible.

Academic Integrity

Academic honesty is required in all your work. Under no circumstances may you hand in work done with or by someone else under your own name. Discussing ideas and approaches to problems with others on a general level is encouraged, but you should never share your solutions with anyone else nor allow others to share solutions with you. You may not examine solutions belonging to someone else, nor may you let anyone else look at or make a copy of your solutions. This includes, but is not limited to, obtaining solutions from students who previously took the course or solutions that can be found online. You may not share information about your solution in such a manner that a student could reconstruct your solution in a meaningful way (such as by dictation, providing a detailed outline, or discussing specific aspects of the solution). You may not share your solutions even after the due date of the assignment.

In your solutions, you are permitted to include material which was distributed in class, material which is found in the course textbook, and material developed by or with an assigned partner. In these cases, you should always include detailed comments indicating on which parts of the assignment you received help and what your sources were.

When working on quizzes, exams, or similar assessments, you are not permitted to communicate with anyone about the exam during the entire examination period (even if you have already submitted your work). You are not permitted to use any resources to complete the exam other than those explicitly permitted by course policy. (For instance, you may not look at the course website during the exam unless explicitly permitted by the instructor when the exam is distributed.)

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook:

"Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

This policy applies to all course work, including but not limited to code, written solutions (e.g. proofs, analyses, reports, etc.), exams, and so on. This is not meant to be an enumeration of all possible violations; students are responsible for seeking clarification if there is any doubt about the level of permissible communication.

The general ethos of this policy is that actions which shortcut the learning process are forbidden while actions which promote learning are encouraged. Studying lecture materials together, for example, provides an additional avenue for learning and is encouraged. Using a classmate’s solution, however, is prohibited because it avoids the learning process entirely. If you have any questions about what is or is not permissible, please contact your instructor.

Academic Accommodations

If you believe you need accommodations for a disability or a chronic medical condition, please contact Student Disability Services (via email at studentdisabilityservices@swarthmore.edu) to arrange an appointment to discuss your needs. As appropriate, the office will issue students with documented disabilities or medical conditions a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact Student Disability Services as soon as possible.

For details about the accommodations process, visit the Student Disability Services website.

To receive an accommodation for a course activity, you must have an official accommodation letter from the Office of Student Disability Services and you need to meet with course staff to work out the details of your accommodation at least two weeks prior to the activity.

You are also welcome to contact any of the course staff privately to discuss your academic needs. However, all disability-related accommodations must be arranged, in advance, through Student Disability Services.