CS 574: Randomized Algorithms — Fall 2026

Sariel Har-Peled (sariel at illinois.edu)

Homework 4

Due Date: Friday, November 20, 2026 at 11:59pm

Submission: Single PDF on Gradescope

Download: hw_04.pdf

Instructions & Course Policies


Problems

  1. Problem 1: Counting Distinct Elements [100 pts]
  2. Problem 2: Random Partitions and Metric Embeddings [100 pts]
  3. Problem 3: Dimension Reduction: What Does One Map Preserve? [100 pts]
  4. Problem 4: Entropy and Compression [100 pts]

← Back to Homeworks