Topic	Chapter(s)	Approximate Time
Introduction, Simple Randomized Algorithms	1-2	1-2 weeks
Moments, Deviations, and Random Sampling	3	1 week
Tail Bounds	4	1 week
Balls, Bins, and Random Graphs	5	1 week
Probabilistic Method	6	1 week
Markov Chains and Random Walks	7	1-2 weeks
Entropy	10	1 week
Monte Carlo Method	11	1-2 weeks
Pairwise Independence and Universal Hashing	15	1-2 weeks

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 not use ChatGPT or any AI to help you solve homework problems.

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.