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.