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.

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

Lecture 36: 04/27/2012

Pollard’s Rho Algorithm and Integer Factorization.

Suppose you’re given a number n = p*q where p and q are large primes. We’d like to factor n efficiently, say O(\sqrt(p)) where p <= q.

We bounced a couple ideas around like the grade school method of factoring a number, or even using the birthday problem. However, these don't give us a good enough running time.

At last we came to the idea of Floyd's cycle-finding algorithm and using it to factor our number n. We start with two pebbles, one slow the other fast, at x_0, and at each step we compute x_slow = f(x_slow) and x_fast = f(f(x_fast)). If we find that x_slow == x_fast, then we've found a cycle.

Supposing we know p ahead of time, we use a pseudo-random generator, e.g., f(x) = x^2 + 1 (mod p), to generate a sequence of integers. Pollard's algorithm is a modified Floyd's algorithm, we compute d = gcd(|x_slow – x_fast|, n). If d != 1, then we've found a non-trivial factor of n, unless of course x_slow == x_fast.

The time until x_slow == x_fast is the length of the transient segment, plus at most the length of the cycle. In total, this adds up to about \sqrt(p), so the algorithm terminates in the correct running time. If it returns an answer, it is correct, however, there is a non-zero probability that the algorithm will not return an answer at all.

There was one last topic we wanted to cover, although we didn't have time. What if you want to generate a random number AND know its factorization. There is a nice randomizing algorithm to generate some large n and its prime factorization. If you'd like to see it, let me know and I'll write up a nice post about it.

Also, Professor Blum will not be giving any more lectures next week, but we can still organize some lectures with students on Wednesday and Friday to see something new. If anyone is interested in learning about something, let me know and we'll make it happen.

Our last class will be on Monday, taught by Steven Rudich. Please remember to sign up for a final exam slot starting on Tuesday. I will make a separate post for the exam requirements.

Lecture 35: 04/25/2012

Today: Matrix Multiplication and Set Equality

We have a nice implementation of a fast matrix multiplication algorithm, say the Coppersmith-Winograd algorithm, which runs in O(n^2.38). Its unbelievably complicated and you’d like to know if it even computes the correct answer.

How could you verify the answer? Well we could just do the vanilla matrix multiplication, but that runs in O(n^3) time, which would defeat the purpose of having a faster algorithm. How do we do better? I have an idea! Let’s try a randomizing algorithm!

Note, that matrix multiplication is associative. One thing we can do is choose a random vector r \in 2^n (flip coins, look at the stars). Compute (A*B)*r = A*(B*r) = A*d = e in O(n^2) time. Likewise, compute C*r = f in O(n^2) time. We can show that if A*B != C, then e != f with probability at least 1/2.

Since this is one of the final exam questions, make sure you understand all of the details!

I’ll be making a separate post for the final exam so that everyone understands what they have to do.

Lecture 34: 04/23/2012

The Final: 1/2 hour meeting with the professor to discuss some problems

I’ll make a Doodle registration link soon and you’ll sign up for meetings just like last time. However, we’ll have 30 minutes each and make sure there’s time for a restroom break and lunch.

The problems are listed on the boards so don’t put off studying!

Today’s topic (at the end): A randomizing algorithm to detect if an error in transmission of a string occurred.

It has a similar flavor to Schwartz-Zippel theorem for testing if a polynomial is identically zero. However, the latter used the fact that a polynomial can only have so many roots, the former uses the Chinese Remainder Theorem under the hood.

Its a nice application of the CRT so make sure you take a look!

Lecture 33: 04/18/2012

Another go at perfect matchings but this time, we want to look at bipartite graphs. The difference is we don’t want to use Tutte’s theorem to help us. So what can we do?

We may proceed using an idea similar to the Tutte matrix. However, since the graph is bipartite, the Tutte matrix will have many zeroes. Therefore, we may simplify out representation of the adjacency matrix.

At the end we saw a neat application of using the inverse of our simplified matrix to tell us about the matchings in the graph.

I’m uploading the pictures of the chalk boards, but as a special treat, we get to look at Prof. Blum’s personal notes. If these are helpful please let me or the professor know.

Lecture 32: 04/16/2012

More Matching. It’s starting to seem like perfect matchings are everywhere in computer science.

Lots of examples with graphs and Tutte matrices. We also looked at what the determinant of a Tutte matrix actually tells you about a graph when you compute it all out. Surprisingly, it tells you more than just perfect matchings. If will tell you if there is a Hamiltonian cycle in a graph.

So what? Well now we know that computing a determinant symbolically is at least as hard as determining if a graph has a Hamiltonian cycle, which is NP-complete. That’s hard, let me tell you.

Lecture 31: 04/13/2012

A recap of Wednesday’s material at the beginning. We changed our definition of the degree of a multivariable polynomial slightly to make the proof of the Schwartz-Zippel Theorem a bit simpler.

Let f(x_1, …, x_n) be a polynomial in n variables from some field F.

A deterministic algorithm works like this:
Fix d to be the degree of f.

Choose d+1 values of each x_i for 1 <= i 1, and evaluate f(x) for x \in S. If f(x) = 0, then there’s at most a 1/k probability the function is identically zero. If we repeat this test a few times using elements selected uniformly at random from S, we get a pretty high probability of obtaining the correct answer.

If we extend to multivariate functions, we still choose random elements from a set S of size k*d from the field F where the polynomial is defined. However, we now evaluate f(x_1, …, x_n) for a randomly chosen tuple from S^n. If f(x_1, …, x_n) = 0, we get the same bound of at most 1/k probability of f being identically zero.

Now for another cool application of testing polynomials. Suppose we have a graph G and we want to know if there exists a perfect matching.

A matching is a 1-regular subgraph of G. A perfect matching is a 1-regular spanning subgraph of G. All this means is we pair up vertices where every pair of vertices share an edge, and every vertex appears in exactly one pair.

How do we do this? Well we can look for obvious signs of not having a perfect matching, such as having an odd number of vertices. Ok, but what if I have an even number of vertices? Try all the matchings! Brute force is always the way to go (just kidding).

There’s a deterministic algorithm that runs in O(m sqrt(n)) time, but can we do better using randomization? Yes!

We assign every edge a variable and form an adjacency matrix of the graph G. However, let’s orient the edges arbitrarily and every time we have a 1 or -1, we replace it with the variable of that edge.

Now, we compute the determinant symbolically and if the polynomial is non-zero, it tells us the perfect matchings in the graph. However, computing determinants symbolically is hard, so we can accomplish the same thing by substituting random values of the variables and checking if the polynomial is zero.

Lecture 30: 04/11/2012

I hope the homework went (is going) well!

Tomorrow (today) we’ll be talking about totally different. We’re gonna dive into some randomized algorithms with the Schwartz-Zippel Lemma.

Try to look it up on the internet before class so you’re not totally lost but here’s some basics:

We have a polynomial a_0 + a_1 x + … + a_d x^d that we’d like to check if it’s the zero-polynomial. That’s easy if we have it in coefficient form (just check if they’re all zero!). But what I give you something like (1 – x)(x + 2x^2 -19x^2)…(1 – x^3)? Well you’d have to multiply it all out (which takes exponential time) and check the coefficients.

Schwartz-Zippel thought: what if you check that polynomial of degree d at some random point? If the value is not 0, then the polynomial can’t be the zero-polynomial. If it was zero, then there’s a good chance the polynomial is zero everywhere. So just repeat this test a bunch of times and if you always get zero, then its probably zero.

It gives us some cool applications so look forward to that!

What a great lecture today!

We first looked at the algebraic or deterministic way of determining if a polynomial is identically 0. You just have to check d+1 points for a polynomial of degree d. That’s great! So why bother with the randomized approach?

If you have a polynomial of degree d in two variables, then you have to check (d+1)(d+1) = d^2 + 2d + 1 points. Now it looks like our linear time algorithm is going to pay off.

We’ll look at how the probability bound changes when we go from one variable to several variables on Friday.

At the end, we looked at a very interesting application of this. We have two sets A and B. We want to check if they’re equal. Well, just sort ‘em and check each element one by one. That takes O(n lg n) time, but what if n is huge??

Let A = [a_0, ..., a_(n-1)] and B = [b_0, ..., b_(n-1)]. Let P_A = (x – a_0)(…)(x – a_(n-1)) and P_B = (x – b_0)(…)(x – b_(n-1)). Now we can check if A = B by asking if (P_A – P_B) == 0. Using our probabilistic algorithm, we can pull this off in linear time and get the correct answer with very very very high probability.

Lecture 29: 04/06/2012

A slight modification to statement of the theorem today.

All we care about is that we get one set A such that: n/3 <= |A| <= 2n/3. The original statement follows from this one but it allows us to focus on getting a small partition into A, S, and the rest of the graph.

We had a little review of the previous lecture material but today's focus is on partitioning the set between t_0 and t_2 (defined last time).

First, we add an artificial vertex "s" and put in edges to every vertex of L(t_0) and keep the BFS tree from before up until L(t_2). The depth of this new tree, T, is at most sqrt(n) because t_0 and t_2 were chosen so that t_2 – t_0 <= sqrt(n).

We'll triangulate T and start with an two paths starting at s to a leaf in L(t_2). The vertices along these two paths will be part of the separator set S. For each vertex in T, we can calculate the number of vertices interior and exterior to the separator set using some sort of dynamic programming. We shrink the interior until we have at between n/3 and 2n/3 vertices in it.

We'll probably get another lecture on the separator theorem and cover some applications of it. Please review the boards and the book for Monday's lecture.

Lecture 28: 04/04/2012

Planar Separator Theorem.

Last time, we covered the main definitions associated with the statement of the theorem and today we dove into the proof/algorithm.

The algorithm is somewhat involved and consists of quite a few steps.

First, we need to embed the graph G in the plane (using our linear-time Hopcroft-Tarjan algorithm), otherwise it wouldn’t make sense to try and separate this graph in the plane.

We run a BFS traversal starting at an arbitrary vertex v and assign to each vertex its BFS level. We denote the vertices at the kth level by L(k). Since edges in a BFS traversal only go between vertices in the same level or adjacent levels, any such set L(k) is actually a separator.

We’ll look at level t_1, which is the “middle” level, i.e., the one containing the (n/2)th vertex in the traversal. If the size of L(t_1) is at most 4 sqrt(n), then we’re done, since it separates the graph into two components, A and B, where each is the set of vertices in levels before and after t_1, respectively. We also know that each of these has at most n/2 vertices.

Alas, this isn’t always the case in algorithms. So what if L(t_1) is too big? We’ll find levels t_0 t_1 as close as possible to t_1 so that the size of L(t_0) and L(t_2) is no bigger than sqrt(n).

What do these give us? We now have three partitions of the BFS tree into C, D, and E of vertices before t_0, between t_0 and t_2, and after t_2, respectively.

If the size of D is at most 2n/3, then we’re done. Why?

Say D has at least n/3 vertices, then the other two sets have at most 2n/3 vertices among them, so we take A = D and B to be the union of C and E. The separator in this case is just the disjoint union of L(t_0) and L(t_2).

If D has less than n/3 vertices, then one of the other two sets must have at least n/3 – O(sqrt(n)) vertices, otherwise we violate the law of conservation of mass and lose some vertices. WLOG, say this set is C, then we let A = C and B is the union of D and E.

Are we done yet?? We still need to consider the case that D is bigger than 2n/3. At least it shrunk by a little bit, so as we noted in lecture, we could just recurse and build A, B, and S that way.

Another way to deal with D is to split it “in half” once and be done with it.

We’ll finish up the proof on Friday. Study the cases well and bring any questions to class or ask them here.