1. (M+U ex. 1.18) Suppose that the function f takes an argument from 0 to n-1 and returns a value from 0 to m-1, for some parameters n and m. Suppose also that, for any x and y in the domain of f, f((x+y) mod n) = (f(x) + f(y)) mod m. Unfortunately, our only access to f is by a table F of its values, up to n/5 of which have been corrupted, so that we don't know for any particular x whether the table value F[x] is equal to f(x) or not. Describe a randomized algorithm that allows us to compute f(x) anyway, with probability at least 1/2 of returning a correct answer, using as few table lookups and as little computation as possible.

2. (M+U ex. 1.22) Let S be a set of n elements. Suppose that we choose two subsets A and B of S, independently of each other, with all 2^n sets equally likely to be chosen. What is the probability that A is a subset of B? (Hint: use the fact that A and B may be chosen by flipping a fair coin for each element to determine whether that element is in or out of the subset.)

3. (a) Suppose we have a randomized algorithm R for answering some yes-or-no question. Algorithm R has probability 1/3 of making a wrong answer: that is, if the correct answer is yes, it answers yes with probability 2/3 and no with probability 1/3, and if the correct answer is no, it answers yes with probability 1/3 and no with probability 2/3. If we make three independent runs of algorithm R, and return the majority of the answers it gives, what is the probability that the answer we return is correct?

(b) How would the answer to part (a) change if algorithm R instead has probability 1/2 of making a wrong answer?