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!