Managing Software Development
Project 5: Building the core of SDG(CSP)
Spring 2008
Karl Lieberherr  
Out: Feb. 15, 2008

Due date: Feb. 25, 2008 

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.
The data-binding technology we use is DemeterJ because it
is simpler than XMLBeans.
Use
http://www.ccs.neu.edu/home/lieber/courses/csg110/sp08/project/project5/csp/
as starting point.
Use the TUCombiner class that has been recently added to DemeterF.

We use the following example using a short-hand notation:
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 1:
===========================================================
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)=7/11

PART 2:
===========================================================
Compute the type T(F) of a CSP formula F.
Type T(F) = (2,22)

PART 3:
===========================================================
Compute the weighted fraction WF(F) of constraints of each 
occurring type in a CSP formula F.
WF(F) =
2:  2/11
22: 9/11

PART 4:
===========================================================
Compute the Shannon cofactors of a CSP-formula F.
Given F, we want to compute F_x and F_x'
according to the formula:

F = x \cdot F_x + x' \cdot F_x'

This is a generalization of project 3, part 2.

Use Ahmed Abdelmeged's relation code in

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

PART 5:
===========================================================
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 5 make a software development plan that you implement during the week.


PART 6:
===========================================================
You are the manager of a software development 
project and one of your junior employees
cannot figure out why the Java program in:
/home/lieber/.www/courses/csg110/sp08/project/project5/csp
does not work correctly.

Write down the advice you give him to find the bug and
provide a few paragraphs of discussion how DemeterF should
be changed to prevent this kind of bug happening in the future.


PART 7: Continuous Integration
==============================

Correct your player for SDG(CNF) that you submitted earlier
based on its behavior in the previous competition.
Also update it to SDG(CSP) using the exchange language defined by:
/home/lieber/.www/courses/csg110/sp08/project/project5/csp
In this exchange language we use relations to represent the CNF clause types.
So we can still transmit CNFs but with a different syntax.
There is no need to keep the old CNF notation.

Resubmit your build of the algorithmic player for the modified pay feature:
pay(d,J,F) = fsat(J,F) > d.price ? 1 : 0
from project 2. We called this version of the game:
SDG-SP08-all-or-nothing(CSP).
Put your revised algorithmic player for SDG-SP08-all-or-nothing(CSP)
into CCIS directory:

/scratch/lieber/sdg/comp2

by Thursday, Feb. 28, 10 pm. Create a directory called 
LastName1_LastName2_LastName3 and put your player and 
additional files it might need into that directory.
If there are only 2 members of the team, you mention
only 2 last names. Use the last names in sorted order.

Your player will be taken from there
and entered into a competition.
The goal of this competition is to get all communication issues worked out.
Money making comes later.