16.5 Homework 3a Bloom Filter Functions are important mechanism for encapsulation and code reuse. They allow you to abstract away the messy details of how things are implemented so that you can concentrate on the algorithm you are working on. In this homework, you will practice writing functions by implementing an interesting algorithm called a "Bloom Filter". There are two problems in this homework. Related C++ HackerRank Problems o Introduction->Functions Bloom Filter From https://en.wikipedia.org/wiki/Bloom_filter: A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not-in other words, a query returns either possibly in set or "definitely not in set'. Elements can be added to the set, but not removed (though this can be addressed with a counting filter); the more elements that are added to the set, the larger the probability of false positives The Bloom filter itself is stored as an array of m Boolean values, which all start out as false. To add an object to the filter (in our case strings), we compute k hash functions for the string, and set the bit at the hash indices to true To test if a string is in the filter, we compute the k hash functions for that string and check to see if the values stored at those locations in the filter are true or false. If any of them are false, then the string is definitely not in the set, but if they are all true then the string is probably in the set. Fairly rigorous analysis has been done on the error rates of Bloom filters (some of which is described in the Wikipedia article), but a quick rule of thumb is that using 10 bits per item stored in the filter and 7 hashes (k-7) will result in a false positive rate of about 1% The final functionality needed to implement the Bloom filter is the hash functions themselves. For a String s with letters so...(n-1), a positive integer p, and a Bloom filter of size m, we can define a hash h p(s) as