Citation Youtube Harvard University

Hashing is covered. Load balancing, independence. Dictionary, perfect hashing, linear probing. The retrieval problem. Cuckoo hashing. Membership Bloom filters

Family H of functions Mapping {u} -> {m] There is a set S c subset of [u}| |S| = n such that we wasn't some of H we pic to "behave on S. They are hashed, and there can be collisions.

There are N jobs that need to be assigned to M machines. Each job Id in [u].

Algorithms | Harvard Lecture Online Lesson 3 Comp Sci Load Balancing

When a new job comes, it gets processed. When a new job j [u] comes, have it processed by y machine h (,)

Called the "balls" and bins random process. Its a load balancing across machines.

Then Chernoff, Suppose Xi, Xn indep X 0,1 Ex = pi

(X = Sum n Sigma i-1 Xi

Probability P of X being > or equal to 1 +s ex) e 1 +s delta to the expectation of S

Suppose M = N

Prpbablity M Clogn over log Logn n Jobs. < at most 1 over poly n.

pf is the turnoff bound

Family H of functions

Mapping [u] to [m]