3. Suppose we are given a propositional formula with n variables (called 3SAT expression) which is of the following form: A clause is the OR of 3 distinct variables and a 3SAT expression is the AND of a bunch of clauses. We want to find an assignments of true and false values such that each clause is satisfied or output that no such clause exists. It is known that this cannot be solved unless we look at all 2n assignments (a) Find a randomized algorithm (i.e we do something in a random manner in our algorithm) such that if we let X be the random variable that denotes the number of satisfied clauses we have that E[X(if there are m clauses). Hint: It may be MUCH simpler than you think. (b) For your algorithm prove that PX nr Hint: Use Markov's inequality on 3. Suppose we are given a propositional formula with n variables (called 3SAT expression) which is of the following form: A clause is the OR of 3 distinct variables and a 3SAT expression is the AND of a bunch of clauses. We want to find an assignments of true and false values such that each clause is satisfied or output that no such clause exists. It is known that this cannot be solved unless we look at all 2n assignments (a) Find a randomized algorithm (i.e we do something in a random manner in our algorithm) such that if we let X be the random variable that denotes the number of satisfied clauses we have that E[X(if there are m clauses). Hint: It may be MUCH simpler than you think. (b) For your algorithm prove that PX nr Hint: Use Markov's inequality on