COMP4600/8460 - Advanced Algorithms S2 2022 Assignment 3

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

P (Sn  ≤ (1 − δ)np)    ≤   e

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 (M(n))()M

2. Show the probability that all n bins have at most M balls is at most n()

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  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 P(X > nlnn + cn) = 1 − e −e − c

n →∞

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