# Finding randomized and deterministic algorithms for the assignment of clauses of a k-CNF Boolean formula

Let a Boolean formula $\varphi$ in K-CNF with $m$ clauses be given as an input.

The goal of an algorithm is to find an assignment satisfying at least $m(1-2^{-k})$ clauses of $\varphi$.

I need to find:

1. A randomized algorithm and estimate its expected time
2. A deterministic algorithm and argue about its correctness using the method of conditional expectations

Here are my thoughts about approaching the design of algorithms for this purpose:

Randomized algorithm:

• assigning Boolean values randomly to Boolean variables, counting satisfied clauses
• Finding the expected number of satisfied clauses
• Iterate through as much as is needed

Deterministic algorithm:

• Considering Boolean variables one by one
• For a given variable $p$, count how many clauses, that have not been made true yet, are made true by setting $p$ true, and how many by setting $p$ false

• Act "greedily"

Does anybody have an example of what such an algorithm would look like in both cases? I don't really have an idea of where to start.