Algorithms and Data
Spring 2010

Due date: February 24, 2010
At beginning of lecture

The midterm will be on February 24th.


Problem 6:

We continue the theme from problem 5 
using material from the Randomized Algorithm Chapter

Decision Problems versus Search Problems
or
Making existence arguments efficiently constructive
==================================================================

Read material in chapter 13:

Read 
Introduction
13.1 Contention Resolution
13.3 Random Variables and their Expectations
13.4 Randomized Approximation Algorithm for MAX 3-SAT

Specifically, the probabilistic method on page 726.

Make randomized algorithm deterministic.
Greedy algorithm correctness is based on recurrence relation.
Make non-constructive proof efficiently constructive.

As 13.16, page 727 shows, we might have to do many iterations
of the randomized algorithm (8*k for MAX 3-SAT with k clauses).
Therefore we want to turn the randomized algorithm
into a regular efficient algorithm.

The key to this is a recurrence relation for the expected
number of satisfied constraints. This is very similar
to dynamic programming  where you might start with a recurrence relation
involving subproblems.

Boolean CSP is a generalization of Satisfiability where the clauses are 
defined in terms of a set of Boolean relations. 3-Sat only uses
OR relations with 3 distinct variables while 3-CSP may use any
of the 256 Boolean relations of arity 3.
In the following, CSP refers to Boolean CSP where the relations
are of arity 3.

For a weighted CSP formula F and Z(F,b) a random variable dependent on F
giving the number of weighted satisfied constraints
under coin bias b, we define E(Z(F,b)).

Can we define E(Z(F,b)) in terms of two subproblems?
Consider F[x=0] and F[x=1] to be the two Shannon cofactors of F
so that the following recurrence holds:

F = (!x and F[x=0]) or (x and F[x=1])

Can you come up with a recurrence for E(Z(F,b))?

Consider 

E(Z(F,b)) = UNKNOWN1(b) * E(Z(F[x=0],b)) + UNKNOWN2(b) * E(Z(F[x=1],b))

Find UNKNOWN1(b) and UNKNOWN2(b).

Turn the recurrence into an efficient algorithm that is
guaranteed to find an assignment which satisfies >= E(Z(F,b)).

Part 1:
=======

Turn in UNKNOWN1 and UNKNOWN2 
and your deterministic algorithm that finds an assignment
satisfying the fraction 7/8 of all clauses.


Part 2:
=======

Consider the Boolean relation 1in3 (one in three)
which is defined by the following truth table:

000
001 1
010 1
011
100 1
101
110
111

What is the expected number E-1in3 of satisfied clauses
in a MAX CSP problem that uses 1in3 if a fair coin (bias b = 1/2) is used?
Design a deterministic algorithm that
finds an assignment with quality E-1in3.

Part 3:
=======

Is there a better bias for part 2 than b = 1/2?
What is the maximum bias which gives the best expected value?

For part 3 you are invited to play the SCG.
The hypotheses are of the form:
In a 1in3 formula the fraction f of the clauses can always be satisfied.