Two multisets of numbers are equal if they contain the same numbers with the same multiplicities, e.g., {1, 2, 1} and {2, 1, 1} are equal, but {1, 2, 2} is not. We can test if two multisets of size n are equal by sorting in O(n log n) or by hashing, but here is another method. For a multiset S = {e1, e2, . . . , en} define P(S) = (x e1)(x e2) (x en), a polynomial in one variable x. (a) [3 marks] For multisets S1 and S2 prove that S1 = S2 iff P(S1) P(S2). (You may quote results from linear algebra without proof.)

(b) [7 marks] Based on this, and on the Schwartz-Zippel result from class, suggest a randomized Monte Carlo algorithm to test if S1 = S2. Your algorithm should have error probability at most 1/2. Be clear about the range of your random numbers. On which side are the one-sided errors? Analyze the run-time of your algorithm, assuming arithmetic operations take constant time. For practicality, your computations should be done modulo a small prime, but you do not need to analyze how large a prime is needed.

2. 10 marks] Two multisets of numbers are equal if they contain the same numbers with the same multiplicities, e.g., 1,2,1) and 2,1,1 are equal, but 1,2, 2 is not. We can test if two multisets of size n are equal by sorting in O(n log n) or by hashing, but here is another method For a multiset S e, e... en) define P(S)(-e( - e2)(x -en), a polynomial in one variable r. (a) 3 marks] For multisets Si and S2 prove that S1-S2 iff P(Si) P(S2). (You may quote results from linear algebra without proof.) (b) [7 marks] Based on this, and on the Schwartz-Zippel result from class, suggest a ran- domized Monte Carlo algorithm to test if Si-S2. Your algorithm should have error probability at most 1/2. Be clear about the range of your random numbers. On which side are the one-sided errors? Analyze the run-time of your algorithm, assuming arith- metic operations take constant time. For practicality, your computations should be done modulo a small prime, but you do not need to analyze how large a prime is needed. 2. 10 marks] Two multisets of numbers are equal if they contain the same numbers with the same multiplicities, e.g., 1,2,1) and 2,1,1 are equal, but 1,2, 2 is not. We can test if two multisets of size n are equal by sorting in O(n log n) or by hashing, but here is another method For a multiset S e, e... en) define P(S)(-e( - e2)(x -en), a polynomial in one variable r. (a) 3 marks] For multisets Si and S2 prove that S1-S2 iff P(Si) P(S2). (You may quote results from linear algebra without proof.) (b) [7 marks] Based on this, and on the Schwartz-Zippel result from class, suggest a ran- domized Monte Carlo algorithm to test if Si-S2. Your algorithm should have error probability at most 1/2. Be clear about the range of your random numbers. On which side are the one-sided errors? Analyze the run-time of your algorithm, assuming arith- metic operations take constant time. For practicality, your computations should be done modulo a small prime, but you do not need to analyze how large a prime is needed