1. Consider the following algorithm for the 2-SAT problem. Given a 2-CNF formula φ, start with an arbitrary truth assignment a.
for i = 1 to t
if a satisfies φ then return a, else find a clause C falsified by a and flip a randomly
chosen bit of a corresponding to a literal from C return ‘unsatisfiable’.
Show that for t = O(n2) if the formula is satisfiable then the algorithm finds a satisfying truth assignment with probability at least 99 %. (Why does this approach fail for 3-SAT?)
Hint: This is a randomized version of the 3n/2 algorithm for 3-CNF satisfiability, applied to 2-CNF. How does the distance of a and a fixed satisfying truth assignment change during the algorithm? Relate this to a random walk on a line, which starts at distance i from the origin, and in each step moves with probability 1/2 to the left or to the right. Consider ti, the expected time of getting to the origin. In general,
ti = ti−1 +ti+1. 2
2. a)ConsiderthegreedyalgorithmforMAX-SAT:repeatedlypickavariableandsetittothevalue which satisfies more clauses. After setting a variable simplify the formula in the natural way. Ties are resolved arbitrarily. Show that the algorithm is a k/(k + 1)-approximation algorithm for CNF expressions where every clause contains at least k literals.
Hint : argue similarly to the analysis of the greedy algorithm. Here a clause has to shrink at least k times to be falsified.
b) Consider the following modified greedy algorithm for the MAX-SAT problem: repeatedly pick a variable and set it to true or false depending on whether clauses containing the variable or its negation have larger total weight. Here the weight of a clause C containing l literals is 1/2l. Ties are resolved arbitrarily. After setting a variable, simplify the formula in the natural way.
For example, for the formula (x∨y)∧(x∨y ̄∨z)∧(x ̄∨u)∧(x ̄∨z ̄), clauses containing x have weight 1/4 + 1/8 = 3/8 and clauses containing x ̄ have weight 1/4 + 1/4 = 1/2. So x is set to 0 and the formula is simplified to y ∧ (y ̄ ∨ z).
Show that the modified greedy algorithm is a (1 − 1/2k)-approximation algorithm for CNF ex- pressions where every clause contains at least k literals. Consider how the total weight of clauses changes after an iteration.
7. Consider the following algorithm for the unweighted MAX-CUT problem on a graph G = (V, E):
start from an arbitrary partition of V
while there is a vertex v such that moving v to the other side increases the cut do
move v to the other side
Show that the algorithm runs in polynomial time and it is a 1/2-approximation algorithm.
11. Consider the following algorithm for testing the monotonicity of an array of size n: for i = 1 to t
pick a random position j ≤ n − 1 if A[j] > A[j + 1] then reject
accept
Show that t has to be Ω( n) in order to get a correct property testing algorithm.
√