Let A be the following algorithm for determining whether a polynomial is identically zero or not: Input: a polynomial Q(z), an integer N. Output: zero or non-zero. Algorithm 1. Choose an integer r at random from the interval [1..N]. 2. Evaluate Q(r). If Q(r) = 0 return zero, otherwise return non-zero.

Answer following:

1. The algorithm A returns either zero or non-zero. Which of them is always correct and which may be incorrect? 2. Suppose that you can run A only once. If Q has degree at most 10, how large must N be to guarantee that the probability of error is less than or equal to 1%? 3. Suppose that N = 50 is fixed. Suppose also th