Probabilistic foundations and basic algorithms: RP and BPP, Min Cut, tail inequalities, randomized selection, pairwise independence (2 weeks).

More probability and algorithms: Balls and bins, randomized routing, martingales, probabilistic method, derandomization (2 weeks).

Randomized compression: Sketching, dimension reduction, sparsification, matrix Chernoff (2 weeks)

Combinatorial optimization and approximation algorithms: Linear programming in small dimension, randomized rounding, semidefinite programming and Max Cut (2 weeks).

Algebraic techniques and isolation: Fingerprinting, polynomials, matching and isolation lemma, primality testing (2 weeks).

Random walks and the Monte Carlo method: Hitting and cover times, Undirected s-t Connectivity, expanders and mixing times, probability amplification, approximating #DNF, Markov chain Monte Carlo (3-4 weeks).

Pseudorandomness: Pseudorandom generators and randomness extractors (1 week).

• Discrete Probability, at least at the undergraduate level;
• Linear algebra, including vector spaces and eigenvectors/eigenvalues;
• Combinatorics, at least basic combinatorics and graph theory;
• Algorithms, including their analysis and the notion of polynomial time.

Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. Discussion of homework problems may include brainstorming and verbally walking through possible solutions, but should not include one person telling the others how to solve the problem. In addition, each person must write up their solutions independently, and these write-ups should not be checked against each other or passed around or emailed. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.

Use of AI: You may use AI to help you understand material. However, you may not use AI to solve the homework problems for you. If you want hints for the homework, ask the professor.

Submission policy: Each student has two late days that they can use during the semester with no penalty (one assignment two days late, or two assignments one day late). Once late days are used up, no credit will be given for late assignments. A day here means 24 hours. The weekend doesn't count, so Friday to Monday counts as one day. I may not allow late days for certain assignments.