Randomized k-SAT algorithm

Consider an instance of SAT with $m$ clauses, where every clause has exactly $k$ literals.

• Give a Las Vegas algorithm that finds an assignment satisfying at least $m(1-2^{-k})$ clauses, and analyze its expected running time.
• Give a derandomization of the randomized algorithm using the method of conditional expectation.

0

0

0

0

0

0

0

0

0

0