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.

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

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

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