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.
