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.)