This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
The following article was written in 1984 as a non-technical "column" in a research journal:
"The NP-Completeness Column: An Ongoing Guide", David S. Johnson
Don't be intimidated by the title, or if you don't understand every word. I want you to read the first two sections of this article (up to page 6), which is mostly a summary of a number of problems where the randomized algorithm is faster than the best known deterministic one.
THe problems that are mentioned include: testing if a number is prime, finding the closest pair of points in a square region, determining whether two sets of polynomials have the same product, factoring polynomials, and determining whether two graphs are equivalent ("graph isomorphism").
After reading the first two sections, pick one of the problems that is mentioned. Then do three things: