Homework 1
Due Date: Wednesday, September 23, 2026 at 11:59pm
Submission: Single PDF on Gradescope
Download: hw_01.pdf
Instructions & Course Policies
- Collaboration Policy: You are encouraged to work in groups of up to three students. However, each student must write up their solutions completely independently in their own words. You must explicitly list all group members and external resources consulted on the first page of your submission.
- AI Policy: You are welcome to use AI agents to help you format your homework solution or consult on the solution.
- 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: Solutions must be self-contained, mathematically rigorous, and as simple as possible. Clearly define all sample spaces, random variables, events, and invariants used.
- Grading: This problem set contains 4 problems, each worth 100 points, for a total of 100 points. You have to solve only one problem. You are encouraged to think about all of them, as they are fair game for the midterm.
Problems
- Problem 1: The Lazy Susan, the Blindfolded Diner, and the Alias Cafeteria [100 pts]
- Problem 2: The Council of Feuding Academics: Expectation, Cuts, and Independence [100 pts]
- Problem 3: QuickSort Under the Microscope: Near-Misses, Extremes, and Medians [100 pts]
- Problem 4: Chebyshev’s Watchdog: Polling, Independence, and the Almost-Median [100 pts]