Suppose that you are trying to write a program that takes as input a number x and that outputs the value of the function mystery(x). Here's what you know about this function:
Its inputs and outputs are both integers in the range from 0 to 99.
For any two numbers x and y in this range, mystery(x + y mod 100) = mystery(x) + mystery(y) mod 100.
Your program has access to an array M[x] of length 100 which originally stored the values of the mystery function: that is, at some point in the past, the array values satisfied the equation M[x] = mystery(x).
Unfortunately cosmic rays have corrupted up to 20 of the array values, replacing them with incorrect numbers.
Describe how to use this information in a randomized algorithm for computing mystery(x), regardless of whether M[x] is or is not one of the corrupted cells. Your algorithm should guarantee that the probability getting a correct answer is at least 1/2. It should use as few table lookups and as little computation as possible.
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?
How would the answer to part (a) change if algorithm R instead has probability 1/2 of making a wrong answer?
Freivald's algorithm checks whether a matrix product is correct by testing it against random vectors of 0's and 1's, but the Schwarz et al method for testing whether a polynomial is zero uses random choices from a larger set of values. Define a bad polynomial to be a polynomial that is not zero, but that appears to be zero whenever all of its arguments are zeros or ones (showing that the larger number of choices used by Schwarz et al is necessary for it to work correctly). For instance, the single-variable polynomial x3 − x is bad, because its value is zero no matter whether x is zero or one. Find a three-variable bad polynomial with as small a degree as possible.
Suppose that we wish to test whether a given polynomial is zero or not by evaluating it at a small number of points, but we wish to do so deterministically (meaning that we don't use any randomization and the result should always be correct). For two-variable polynomials of degree two, how many points do we need to test? Find a set of that many points that suffice for this problem.