Homework 2
Due Date: Tuesday, October 20, 2026 at 11:59pm
Submission: Single PDF on Gradescope
Download: hw_02.pdf
Instructions & Course Policies
- Collaboration Policy: You may work in groups of up to three, but each student must write their solutions independently, in their own words. List all collaborators and external resources on the first page of your submission.
- AI Policy: You are encouraged to use AI agents to help format your solutions, and may also consult them about the mathematics. Declare all textbooks, papers, websites, and AI tools consulted, and explain how you used them, in a footnote or bibliography.
- Submission: Solutions must be typeset in LaTeX and submitted as a single PDF on Gradescope. Start each problem on a new page.
- Clarity and Rigor: Define your random variables and justify each use of independence, conditioning, and a tail inequality. You may use a preceding subpart’s stated conclusion even if you have not proved it.
- Grading: This problem set contains 4 problems, each worth 100 points, for a total of 100 points. You have to solve only one problem of your choice. You are encouraged to think about all of them, as they are fair game for the midterm.
Problems
- Problem 1: From Collisions to Perfect Hashing [100 pts]
- Problem 2: Derandomization: Balancing and Satisfying [100 pts]
- Problem 3: Three Games with Balls and Bins [100 pts]
- Problem 4: Random Interleaving on a Grid [100 pts]