PART 3: ================================================= 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: =========================================================== 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: ? 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, a new relation number and possibly one fewer variable. 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 on the way back of flowing through a constraint. And you need it each time you visit a variable. PART B: =========================================================== 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 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.