# Project 5

CSU 670 Fall 2007
Out: October 5, 2007
Due October 12, 2007

This subproject consists of 3 parts: Producing Raw Materials,
Communication and Coordination and Roadmap.
##
Producing Raw Materials

###
Producing Raw Materials Part 1

To play the Specker Derivative Game well, we need to solve
the following sub problem:
Input: CNF type T
Output: Weighted CNF F of type T in which only a small fraction of the clauses
can be satisfied. CNF F contains max_clauses clauses and max_variables variables.
Postcondition:
Ideally we would like to have an F that minimizes the fraction of clauses that can be
satisfied. Can we achieve such a post condition efficiently?

With our lack of information about what the most difficult raw material of a given type T is,
let's try something that is easy to implement and maybe a good approximation of what we are
looking for. Consider a type T = ((j1,p1) (j2,p2).
The js are the clause length and the ps are the number of positive literals.
Consider one pair of the type and lets call it (j,p). Let's assume that
we have n variables. Let's generate ALL clauses of type (j,p) with n variables.
How many are there: choose(n,j)*choose(j,p) where choose(n,k) is the binomial
coefficient n choose k.

Example:
n=4, j=2, p=1
choose(n,j)*choose(j,p) = 6 * 2 = 12.
Here they are: (one clause per line)
!1 2
1 !2
!1 3
1 !3
!1 4
1 !4
!2 3
2 !3
!2 4
2 !4
!3 4
3 !4

Given a type T = ((j1,p1) (j2,p2) we generate
choose(n,j1)*choose(j1,p1) clauses for the first pair and
choose(n,j2)*choose(j2,p2) clauses for the second pair.
Those clauses are delivered as raw material.
We don't take advantage of assigning weights to the clauses;
currently all clauses have weight 1.
In your own algorithmic player you should choose a clever way
to assign weights to the clauses to make it harder to satisfy
a large fraction of the clauses.

###
Producing Raw Materials Part 2

Use your MAXSAT solver from project 4 to find a satisfying assignment.
Can you manually do better than your solver?
Turn in the outputs from several test runs for different types.
This might actually give you information about how to price
your derivatives when you play the game!
##
Communication and Coordination

Implement a simple Administrator and Player for the
Blackboard Architecture using a
black board in a file system F that we have chosen.
Implement the following sequence of transactions for one turn of the player:
Put all the transactions for one turn as one batch into the blackboard.
The Adminstrator tells the player that it is
its turn by setting a flag in the blackboard.
The Player gets the store.
The player prepares a list of transactions and puts them into the blackboard.
The Administrator collects it and updates the store etc.

##
Roadmap

Document your road map to the final stage of you algorithmic trader.
This is a 1-2 page document,
listing requirements, clarifying issues left open or left contradictory
in the game description document and enumerating the steps you intend to follow.
Explicitly list what components will be developed, their use and
where they fit in the whole scheme of things.
Estimate the time it will take you to finish each component given that you have already
worked on several of the components.