CSU 670 Fall 2008, Software Development				Karl Lieberherr
Out: October 3, 2008
Due: October 10, 2008


PART 1:  3 points
========================================
TESTING

Thorougly test the generic player against our requirement document:
http://www.ccs.neu.edu/home/lieber/courses/csu670/f08/requirements/sdg-f08.pdf
http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/requirements/SDG2.doc

Create a specific player/administrator for CSP that
must use the communication language we selected.
But your specific player is otherwise like the generic player:
it is dumb.

It is very important to keep the generic player clean.
Use the include option for .cd files as shown in:
/home/lieber/.www/courses/csu670/f08/project/genericSDG/ClassicProject

Separate your code for the generic player and the CSP specialization.

----------------------
general.cd
...
only contains generic structure; nothing about Constraints
----------------------

classic.cd 
//cd for generic version

include "general.cd";
RawMaterialInstance = String.
...



If you note discrepancies report them to the class mailing list asap.

/home/lieber/.www/courses/csu670/f08/bhavna/ClassicProject/history.input    
and history1.input
shows sample output from the generic player produced by Bhavna Balani.

What to turn in:
All discrepancies you find with a description how to repair the software.

Your modified player and your modified administrator that implement the requirements.

We will run the first whole class competition with your tested generic players
with the new communication language.

PART 2: 5 points
========================================

Roadmap

By now you have acquired significant knowledge about
the Specker Derivative Game and you know the code
base (the generic player that only knows 
about predicates, raw materials, and finished products without the details)
on which you build. 

Document your road map to the final stage of your algorithmic trader
to be ready in 3 or 4 weeks with ample time to improve its performance
in the artificial market until December.
This is a 1-2 page document,
summarizing requirements, clarifying issues left open or left contradictory
in the requirements 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.
Make a plan for your project.

Estimate the time it will take you to 
finish each component given that you have already
worked on several of the components.

PART 3: 20 points
=================================================

We implement simple functionality that you need for the project.
All implementation is done in DemeterF because the programs
look like designs and can easily be adapted to other structures.

Use our standard notation:
/home/lieber/.www/courses/csu670/f08/project/project3/rawmat

We use the following example using a short-hand notation
(slightly different than our standard):

CSP-Formula F:

5: 22 1 2 3        // 5 is weight, 22 the relation
4: 22 1 2   4
2:  2 1 2   4

PART A: 5 points
===========================================================
Compute the Shannon cofactors of a CSP-formula F for a literal z of variable x.
Given F, we want to compute F_x and F_x'
according to the formula:

F = x and F_x or x' and F_x'

Use Ahmed Abdelmeged's relation class in

http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/project/project4/IR-2.0/doc/

Source code:
/home/lieber/.www/courses/csg110/sp08/project/project4/IR-2.0

The Shannon cofactors are useful for many algorithms.

Flow based design to be implemented in DemeterF:
Flow through the CSP-formula F and build the cofactor F_x
by reducing each constraint by setting x to true
in each constraint. For example, the constraint
5: 22 1 2 3, where 1 is set to true reduces to
5:  ? 1 2 3
where ? is the relation number returned by Ahmed's Relation class.
Reducing a constraint means to create a new one
with the same weight, and a new relation number.
The number of variables remains 3.
The relation number will say which variables are don't care variables.
Note that List.index(...) is useful in this context
and of course the Relation.reduce(...) method.

Computing a Shannon cofactor is a translation from the
language CSP-formula onto itself and therefore calls
for the use of the Bc class.

How do you send the literal z? Use an update method.
You need it when you find the new relation number.



PART B: 2 points
===========================================================
Compute quality(F,J) of assignment J for CSP-formula F.
J = (1,!2,!3,4) // !2 is 2 negated.
quality(F,J) = (5+2/11)=5/11

Flow through the CSP-formula
and use the reduce function from Ahmed's class for each constraint.
Looks like a good use of TUCombiner? The fold is summation.
The leaves are the constraints which reduce to a number.


PART C: 2 points
===========================================================
Compute the set of relations  contained in CSP formula F.
Type T(F) = (2,22)

This is

PART D: 4 points
===========================================================
Compute the weighted fraction WF(F) of constraints of each 
occurring relation number in a CSP formula F.
WF(F) =
2:  2/11
22: 9/11

PART E: 7 points
===========================================================
This part will be useful for improving your 
product finishing agent for SDG(CSP).
We provide you with software written by an outsourcing team
that provides you with an abstraction of CSP-formulas
that is good enough to play the SDG(CSP) game 
optimally. The provided software helps you to translate
a CSP-formula into a polynomial on one variable p.
This variable is a probability which you use to generate a random
assignment with bias p.
A random assignment with bias p is an assignment where 
each variable is set to true with probability p.
The maximum bias is the best probability.

http://www.ccs.neu.edu/home/lieber/courses/csu670/f07/outsourced/guaraldi/satsolver-1.1/api/index.html

The following link points to implementations
http://www.ccs.neu.edu/home/lieber/courses/csu670/f07/outsourced/guaraldi/

It is recommended to use Daniel's or Will's implementation.

Implement the following task:
Input: CSP-formula F.
Output: Coefficients and maximum bias of the polynomial.

Test your program with various CSP-formulas including one
where the type is T=(22). The maximum bias should be
one 1/3 in this case. Is it? 

What should the maximum bias be
for T=(X). Test your hypothesis with a CSP(X)-formula.
Try X = 1, 60, 90, 102.

Are the polynomials for 60,90,102 all different?

For part E make a software development plan that you implement during the week.