Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP4600/8460 - Advanced Algorithms
Assignment 3
[Your Name] ([Your UID]) Date: August 31, 2022
Note: Plagiarism is strictly prohibited. Even though you may discuss with classmates, you should write your
homework assignment by yourself.
1 Questions
Q1) (5 Marks) Let Sn be a binomial random variable BIN(n, p)
Apply Chernoff bound to prove for any 0 < δ < 1 that
P
(
Sn ≥ (1 + δ)np
) ≤ e−δ2np3
P
(
Sn ≤ (1− δ)np
) ≤ e−δ2np2
Q2) (5 Marks) There are n balls thrown independently and uniformly at random into n bins
1. Show the probability that a particular bin receiving at least M balls is at most
(
n
M
)
( 1n )
M
2. Show the probability that one of the n bins has at least M balls is at most n( e
M
MM
)
Note: Do not use Poisson approximation
Q3) (5 Marks) Given a set of strings S = {s1, ..., sn}, map each string to a bit-string using m bits by an
ideal hashing function, such that each bit has an equal probability of being 0 or 1. Then we use the
set of bit-strings B = {b1, ..., bn} to test if a string is a member of S or not
1. Show m = Ω(log n) bits is necessary for the probability of a false positive to be lesser than 1
2. Show m = O(log n) bits is sufficient for the probability of a false positive to be at most 1m
Q4) (2.5 Marks) Let Sn be BIN(n, p). Prove the tail probability is bounded by P(Sn ≥ enp) ≤ e−np
Q5) (2.5 Marks) Let X be the number of draws required to collect all n types of coupons. Prove, for any
constant c,
lim
n→∞P(X > n lnn+ cn) = 1− e
−e−c
You can use Poisson approximation
Q6) (10 Marks) Simulate balls-and-bins model and power of d-choices model, and compare their empirical
maximum loads under various values of m (≤ 10000), n (≤ 10000) and d (≤ 10). Implement your
simulation in Python/Java/C. Plot and discuss the results here in this report, and upload your code
separately on Wattle
1
2 Assignment 3: [Your Name]
2 Answers
. . .
References
[MU] Mitzenmacher & Upfal, Probability and Computing, Cambridge University Press, (2017).