# 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 mm clauses be given as an input.

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

I need to find:

A randomized algorithm and estimate its expected time
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 pp, count how many clauses, that have not been made true yet, are made true by setting pp true, and how many by setting pp 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.

=================

=================

=================