Practice Problem Set 3 Solutions
Suppose that you are given the bitmap representation of a set \(S\) of non-negative integers. Describe how to find the smallest non-negative integer \(x\) that is not a member of \(S\), in a constant number of integer operations.
(This is an important operation in combinatorial game theory, where it is called the “minimum excluded value” or “mex”. It is also needed in graph algorithms for greedy coloring.) You may assume that the dictionary
set2elementfrom the lecture notes has already been computed and that looking up a key-value pair in that dictionary is allowed among the constant number of operations that you perform. You may also assume that the resulting value \(x\) is within the range of values allowed by your bitmap set representation.)Solution:
set2element[(x+1)&~x]; there are many equivalent expressions.Suppose we wish to maintain a set of \(n\) items and a numbering of the items (a function mapping the items to a small range of integers), so that each two items in the set are mapped to distinct numbers, and so that we can look up the number for each item in the set in constant time. If the set changes, the numbering can also change. These numbers could be used, for instance, as indexes into arrays to store information about the items. Describe how to do this using a cuckoo-hash based set representation, without using any more storage space than the set itself would already use.
Solution: Store the items in a cuckoo hash table and use the index of the cell containing \(x\) as the number for \(x\).
The lecture notes include a lower bound showing that (under standard assumptions) it is not possible to handle disjoint-set queries in substantially sublinear time per query, using a data structure whose construction takes polynomial time and space. However, this does not rule out fast queries using bigger and slower-to-construct data structures.
Suppose that:
We are given as input a family of \(n\) sets \(S_i\), each of size \(k\).
Each set is a subset of the numbers from \(0\) to \(N-1\) for some \(N\) (either because they were given that way or because we used the answer to question 2 to number the set elements)
We wish to handle disjoint-set queries of the following form: given a query set \(Q\) of size \(k\), as a list of its elements, answer “yes” if the input sets include a set \(S_i\) that is disjoint from \(Q\), or “no” if no such set exists. When the answer is yes, it is not necessary to find which set \(S_i\) is disjoint.
Describe how to use bitmaps to represent a set-of-sets data structure that can answer disjoint-set queries in time \(O(k)\), using a data structure whose space and construction time is exponential in \(N\). You may assume that operations on \(N\)-bit binary numbers, and that array indexing using numbers of this size, take constant time per operation.
Solution: Represent subsets of the numbers from \(0\) to \(N-1\) as \(N\)-bit integers, and build a bitmap of the \(N\)-bit integers that represent queries that are disjoint from the input sets. It takes \(O(k)\) time to convert a query to the integer that represents it, after which we can simply look up this integer in the bitmap.
We have seen that, to achieve a false positive rate of \(\varepsilon\) for a set of \(n\) items, Bloom filters need \((n\log_2 1/\varepsilon)/\log 2\) bits of storage. We didn't analyze quotient filters and cuckoo filters as precisely, but for the purposes of this problem let's assume that they use \(n(2+\log_2 1/\varepsilon)\) bits. Assuming that this bound is accurate, for which values of \(\varepsilon\) do cuckoo filters use fewer bits than Bloom filters, and for which values of \(\varepsilon\) do quotient and cuckoo filters use more bits? (It is acceptable to solve this numerically by writing a short computer program. Logarithms without subscripts are natural logarithms.)
Solution: Let \(x=\log_2 1/\varepsilon\). We need to solve the equation \[\frac{x}{\log 2}=x+2.\] Subtracting \(x\) from both sides and multiplying by \((\log 2)/(1-\log 2)\) gives \[x=\frac{2\log 2}{1-\log 2}\approx 4.518\] and \[\varepsilon=\frac{1}{2^x}\approx 0.0437.\] For smaller values of \(\varepsilon\) than this, quotient and cuckoo filters use fewer bits than Bloom filters; for larger values of \(\varepsilon\) than this, they use more bits than Bloom filters.