ECE 665 Homework 3
Due by 11:59 PM on Friday, February 25, 2022
Upload to Gradescope, NOT to Moodle
(1) Consider a Bloom lter of n bits, used to evaluate set membership where the set is
of size m bits. The number of hash functions used is k. Suppose that this lter suers
from hardware failure: each bit may be stuck at 0 with probability p0 or stuck at 1 with
probability p1. You may assume (if you need to) that p0+p1 1. Derive an expression
for the false positive and false negative rates for this lter.
(2) Consider the Karger algorithm run on a graph with the following properties. It has
a total of ` disjoint min-cuts (i.e., it contains ` disjoint sets of edges, each of which is a
min-cut), where each min-cut has k edges. The total number of edges in the graph is
e. What is the probability that the algorithm uncovers a min-cut in one run?
(3) This question concerns the Flajolet-Martin algorithm. Suppose you have a stream
with 100 unique values. You use just one hash function (not what is actually done... you
normally need to take multiple hashes and then carry out mean/median calculations
as mentioned in class). What is the probability that your estimate is something in the
range [32, 128]?
(4) Calculate the page rank of each page in a small network consisting of the following
ve pages.
5
1
2
3
4
1