Problem 1:

Let [n] = {1, 2, . . . , n} and g : [n] |→ {-1, 1} be a function and let ∈ < 0.1. We say that g is ∈-good for S ⊆ [n] if | ∑_i∈S g(i)| ≤ n^1-∈.

Give a randomized algorithm that finds g such that for a set S the probability that g is not s-good is at most 1/^n1-2∈. Note that your algorithm does not know the sets S ahead of time (otherwise it is trivial).

Give a randomized algorithm that finds g such that for fixed sets S₁, . . . , S_t with t = n^∈ g is s-good for all sets with probability 1 - o(1).

Note that your algorithm does not know the sets S, S1, . . . , S_t ahead of time.

Hint: use Chebyshev inequality and the union bound.

Problem 1

Let G be an undirected weighted graph with non-negative weights. In class we have learned the randomized algorithm for the MAX-CUT problem such that the expected value of the resulting cut is at least 0.5OP T where OPT is the value of a maximum cut in G. Design a randomized algorithm that runs in polynomial time and finds, with probability at least 0.99, a cut in tt of size X such that X ≥ 0.49OPT.

Hint: Use the Markov inequality.

Problem 2

Explain why ZPP ⊇ RP ∩ coRP. An informal (but correct) argument will be sufficient.

Problem 3

In class we have learned the randomized algorithm for the MIN-CUT problem that finds a minimum cut with probability at least 2/n(n-1) where n is the number of nodes in the graph, n = |V|. The algorithm can be implemented in time O(n²).

Using the aforementioned algorithm design another (simple) algorithm that finds a minimum cut with probability at least 1 - 1/n¹⁰. What is the running time of your algorithm?

Problem 4

Let H be a class of all functions from M to N. Is it true that H is a 2-universal family? Prove your answer. Is it a good idea to use H for applications? Please explain your answer.

Problem 5

In class we have learned how to build a family H of 2-universal hash functions h : M |→ N where |M| = m, |N| = n. Let n > 10¹⁰ be a sufficiently large parameter. Can you construct a family of 2-universal hash functions H such that |H| ≤ 10? Give an example of such family and prove its 2-universality. Otherwise prove that no such family exists.

Problem 7:

Design a randomized algorithm that finds, in polynomial time, all min-cuts with probability at least 0.99. Can you derive an upper bound on the number of different min-cuts?