In the MAX SAT problem, we are given a formula ?? with m clauses over n variables and we want to find a truth assignment that satisfies as many clauses as possible.

Here is a simple randomized algorithm for this problem.

for each variable do

set its value to either 0 or 1 by flipping a coin

end for

(a) Suppose that the j-th clause has kj literals. Give the expected number of clauses satisfied by the above algorithm and provide a lower bound for this number in terms of the input parameters.

(b) Next assume that each clause contains exactly k literals. Give the expected number of clauses satisfied now and provide a lower bound for this number. How does it compare to the lower bound above?

(c) Now de-randomize the above algorithm as follows: instead of flipping a coin for each variable, select the value that satisfies the most as-yet-unsatisfied clauses. Give a lower bound for the number of clauses satisfied by this deterministic algorithm.

Hint: let L_i be the number of clauses containing at least one of the variables {x_1, . . . , x_i}. Show that after i variables have been assigned, the number of satisfied clauses is greater than L_i/2.