15-750 Final Exam May 2000 Manual Blum & Danny Sleator This is a 3-hour closed book exam. Write your answers in your blue books. Problem 1: working with matrices and polynomials: a) (3pts) Evaluate the determinant of this matrix: | 1+x 2+x 3+x | | 1-2x 2-3x 3-4x| | 1+x 1+2x 1+3x| b) What is a resonably good way to check your answer faster and different than recomputing it? c) Give an NC algorithm (poly(n) space, log(poly(n)) time) to solve the following problem: INPUT: An nxn matrix (like the 3x3 matrix above) whose entries are all of the form a+bx with integer coefficients. OUTPUT: The determinant of the matrix; written as a sum or products. d) What difficulties, if any, arise in extending your algorithm to the case where matrix entries are multivariate polynomials (such as 3xy-2z+1)? Assume that each such entry is given as a sum of products, each with integer coefficients and degree d <= n. Problem 2. How to check big arithmetic equations Fermat's Last Theorem asserts that the equation n n n x + y = z has no solution for x,y,z in postive integers for any integer exponent n>2 (for n=2 it has many solutions, e.g. x=3, y=4, z=5). In breaking news, a major newspaper announces a counterexample to Fermat's Last Theorem! The counterexample consists of four large integers x= .., y= .., z= .., n= .., explicitely given, for which it is claimed that n n n x + y = z (Although the newspaper gives the four integers explicitely, it claims that the numbers x^n, y^n z^n are too large to write down completely in decimal notation.) a) There are 10^80 atoms in the universe. How many digits are there in x^n if x and n are both 100 digit numbers? Is this more or less than the number of atoms in the universe? b) How would you efficiently check the alleged counterexample? Give bounds on the running time of your algorithm. Problem 3: Square roots Suppose you have an algorithm for computing square roots modulo a prime. That is, given a number y, your algorithm either finds a solution x to the following equation: x^2 = y (mod p) or it determines that there is no such solution. Show how to use this algorithm to find square roots modulo a number n which is the product of two primes, p, and q. (p and q are known and p != q) Problem 4: Turning out the lights Consider an electronic puzzle consisting of an n by n grid of lights. Each light is actually also a button, and each light is either on or off. When a button is pressed, the light under that button toggles, and in addition some other lights also toggle. Specifically the light to its left, right, above it and below it all toggle. For this purpose the bottom row is adjacent to the top and the left is adjacent to the right. (The topology is that of a torus.) For example, say n=4, and we denote an light that's on by "*" and one that's off by "O". If the * in the diagram on the left is pushed, the result is shown at the right: O O O O * O O O * O O O O * O * O O O O * O O O O O O O O O O O Give an algorithm which takes as input a number n, and an initial state of the lights, and determines if it's possible to turn all the lights off. If it is possible, your algorithm should also computes a sequence of button pushes that achieves this. Express the running time of your algorithm as a function of N, the number of lights (N=n*n). Problem 5: Randomized matchings Here's a randomized algorithm for finding a perfect matching in a graph that has a perfect matching. The algorithm takes a specific type of random walk in the space of matchings until it stumbles across a perfect matching. The algorithm begins with the empty matching and repeats the following step until all vertices are matched: Uniformly at random, pick any unmatched (i.e. free) vertex. Call this vertex x. Uniformly at random, choose a neighbor of x. Call it y. Now add edge (x,y) to the matching. If y was already matched to some vertex, say z, then remove edge (y,z) from the matching. Prove that the algorithm will find a perfect matching with probatility 1. (You need not be concerned with the running time.)