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.

Write-up

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