Question 4:
===========
25 points

Consider Boolean CSP problems based on the following relation R
of arity 3:

000 0
001 0
010 0
011 0
100 0
101 0
110 1
111 0

All clauses of R-formulas use this relation, e.g.

R(x1 x2 x3)
R(x1 x2 x4)
R(x2 x3 x4)

is a sample CSP R-formula.

Compute the expected fraction of satisfied
clauses in an R-formula if each variable is set to true with probability b.

Which algorithm would you use to find an assignment that is
at least as good as the expected fraction?
You may use a deterministic or randomized algorithm.

How would you choose b to maximize the expected fraction?