Monday October 29
To sign up for a problem, send email to alubiw "at" uwaterloo.ca.
I will update this list to indicate the first person who signs up.
- [Thomas Ang]
(from lecture 13)
Show that RP \subset NP. (Part of the presentation should be to explain
RP and NP again. Also explain why you can't easily show NP \subset RP.)
-
[Can Tang]
(from lecture 13)
Show ZPP = RP intersect coRP.
- [Yin Zhao]
(from lecture 14)
Prove: Let f(x_1, . . . , x_n) be a multivariate polynomial of total
degree d. Suppose that f is not identically 0 and that values a_1, . . . ,
a_n are drawn independently and uniformly from a finite set S. Then
Prob{f(a_1, . . . , a_n) = 0} <= d / |S|.
- [Andrei Barbu]
Formulate the following problem as a 2 dimensional linear program:
Given a set of points in the plane, find the best line fitting
the points, where "best" means minimize the maximum vertical distance
of a point from the line. If time, consider other objective
functions, e.g. minimize
the sum of vertical distances of points to the line.
- [Ahren Langschmidt]
Give a polynomial time algorithm for 2-SAT (a deterministic algorithm).