Final Exam

Final Exam:
Schedule a 25 minute meeting with Professor Blum using the Doodle link he sent out.

We’re all assigned a number of questions to write up and prepare for the oral examination. Several questions not requiring a write up are also assigned. The professor is free to ask you about any one of these, so make sure you’ve thought about them at length.


1) Jon Bentley’s Programming Pearls 2.1A
I’ve attached a picture of the problem.

This is a problem from 1986. Ancient! It now being the 21st century, you should be able to solve his problem (both parts) plus solve a more advanced version in which you have just *one* tape drive and only *a few dozen words of main memory*.

2) Towers of Hanoi (graduate version).
Explain how to solve the problem nonrecursively, i.e. without having to maintain a stack. (In case you ever go to Hanoi, you should be able to substitute for a monk who needs to take a break.)

3) Equivalence of 3SAT and Zeroes of a Multivariate Polynomial.
Explain how to transform a set of 3SAT clauses (a product of sums) into a Multivariate Polynomial (a sum of products) such that the clauses are satisfiable iff the Multivariate Polynomial has a zero. The transformation should be efficient (polynomial time).

4) Schwartz-Zippel Theorem.
Explain and prove the theorem (and associated randomizing algorithm) for deciding if a multivariate polynomial is identically zero. Assume the polynomial is given/presented by a black box (an oracle) that takes as input an assignment of the variables and outputs 0 or 1 depending on whether the polynomial is zero on that input or not.

5) Matrix Multiplication Checker.
Explain a randomizing algorithm to solve following problem:

INPUT: 3 n*n matrices A,B,C over either a finite field (e.g. the integers mod p, where p is prime) or an infinite field (e.g. the rationals), and a positive integer k.

OUTPUT: If A*B=C then output “EQUAL.”
else output “NOT EQUAL.”

The probability of error should be less than (1/2)^k and the algorithm should have expected running time O(n^2).

6) No write-up required but please be prepared to discuss:
a) Pollard rho algorithm for splitting composite integers N, or
b) A randomizing algorithm for deciding if two n-bit integers a and b are equal using just O(log n) bits of communication between A (who has a) and B (who has b).