Midterm CSU 670 Fall 2006 Open book and open notes ================================================================ October 24, 2006 Question 1: 51 points Question 2: 20 points Question 3: 30 points Question 4: 15 points Question 4: 61 points 177 points Question 1: Class dictionary design 17 UNKNOWNs: 3 points each: 51 Class dictionary design from example. This models the state language for the transition system behind our project. Consider the following class dictionary and the input sentence. Find the UNKNOWNs: CLASS DICTIONARY RuleStates: ======================================= // Rule States for the project RuleStates = UNKNOWN1 EOF. RuleState : UNKNOWN2 . UnaryS = FailState. BinaryS= UNKNOWN3 UNKNOWN4 UNKNOWN5. AExp : UNKNOWN6. ASimple : UNKNOWN7. ACompound = "(" UNKNOWN8 UNKNOWN9 ")". Concat = ".". FExp : UNKNOWN10. FSimple : UNKNOWN11. FCompound = "(" UNKNOWN12 UNKNOWN13(UNKNOWN14) ")". And = "&". Constraint = "#R" RelationName "(" [PositionLiteral] ")". PositionLiteral = Position Literal. EmptyAssignment = "{}". FailState = "FailState". OptDecisionLiteral = Literal [Star]. Star = "*". Literal = UNKNOWN15. Kind : Neg | Pos . Neg = "!". Pos = . List(S) ~ {S}. // Terminal Buffer Rule FormulaName = UNKNOWN16 Ident. AssignmentName = UNKNOWN17 Ident. Position = int. Variable = Ident. RelationName = Ident. Main = . INPUT SENTENCE: =================================================== // #A: assignment // #F: formula // #L: literal // #R: relation in constraint // UnitPropagate #A M || ( & #F F #R D( 1 #L k ) ) (. #A M #L k) || ( & #F F #R D( 1 #L k ) ) // PureLiteral #A M || #F G (. #A M #L k) || #F G // Decide #A N || #F G (. #A N #L k*) || #F G // Fail #A P || (& #F G #R R()) FailState // Backtrack (. #A M #L l* #A N) || ( & #F F #R C()) (. #A M #L !l) ||(& #F F #R C()) // SemiSuperresolution (. #A M #L k*) || #F F (. #A M #L k*) || (& #F F #R NDL()) // NDL = {The negation of all decision literals in (#A M #L k*)} // Backjump (. #A M #L l* #A N) || (& #F G #R C()) (. #A M #L k) || (& #F G #R C()) // Restart #A M || #F F {} || #F F Question 2: Class Dictionary Design =============================================== 20 points Assume you have a class dictionary for states as described by class RuleState in class dictionary RuleStates (question 1). Extend class dictionary RuleStates so that it accepts the following input. Note that // X state1 state2 has been replaced by: X state1 => state2 Put your NEW class definitions into UNKNOWN1. Don't repeat the classes in class dictionary RuleStates. UnitPropagate #A M || ( & #F F #R D( 1 #L k ) ) => (. #A M #L k) || ( & #F F #R D( 1 #L k ) ) PureLiteral #A M || #F G => (. #A M #L k) || #F G Decide #A N || #F G => (. #A N #L k*) || #F G Fail #A P || (& #F G #R R()) => FailState Backtrack (. #A M #L l* #A N) || ( & #F F #R C()) => (. #A M #L !l) ||(& #F F #R C()) SemiSuperresolution (. #A M #L k*) || #F F => (. #A M #L k*) || (& #F F #R NDL()) // NDL = {The negation of all decision literals in (#A M #L k*)} Backjump (. #A M #L l* #A N) || (& #F G #R C()) => (. #A M #L k) || (& #F G #R C()) Restart #A M || #F F => {} || #F F Question 3: Software Development ================================ 30 points To implement UnitPropagate for relations of rank 3 you need to keep track of the constraints that force one or more variables. Design a program that takes as input a CSP instance and that prints the constraints that force at least one variable. For each constraint that forces at least one variable print the relation number of the constraint. Show the relevant parts of your class dictionary and the program that does the work. Assume you have a function: int forced(int relationNumber, int variablePosition) which returns 0, 1 or -1. -1 means that the variable at variablePosition is not forced. 0 or 1 means that the variable at variablePosition is forced to 0 or 1, respectively. Give enough detail so that it is easy to produce the Java code or give the Java code directly. Put your answer in UNKNOWN1 Question 4: Understanding Requirements Formalism for Project ============================================================= 15 points Prove that the following formula is unsatisfiable using the transition system from the project. (+ is or and ! is negation) 1+2+3, 1+2+!3, !1+4, 1+!2+3, !1+!4, 1+!2+!3 Use the notation from the project description: Start in state: {} || 1+2+3, 1+2+!3, !1+4, 1+!2+3, !1+!4, 1+!2+!3 And end in FailState. Put your answer in UNKNOWN1. Question 5: Program Understanding ================================================================== 25 UNKNOWNs 1- 18: 3 points per UNKNOWN : 54 19-25: 1 point per UNKNOWN : 7 61 Consider the following class dictionary, program, input and output. Find the UNKNOWNs: CLASS DICTIONARY: =========================================================== import edu.neu.ccs.demeter.dj.* ; import java.util.*; TransitionInstance = State States EOF. States = List(SepState) . SepState = "by" RuleName State. State : UnaryS | BinaryS. UnaryS = FailState. BinaryS= Assignment "||" ConstraintSatisfactionInst. FailState = "FailState". Assignment = List(OptDecisionLiteral). OptDecisionLiteral = Literal [Star]. Star = "*". ConstraintSatisfactionInst = List(Constraint). Constraint = RelationName "(" List(Literal) ")". Literal : Pos | Neg common Variable. Pos = . Neg = "!". Variable : VarName | VarNumber. VarName = Ident. VarNumber = Number. RelationName = Number. RuleName = Ident. List(S) ~ {S}. Main = . PROGRAM: ============================================================= Main { {{ public static void main(String args[]) throws Exception { final TransitionInstance m = TransitionInstance.parse(System.in); ClassGraph cg1 = new ClassGraph(true, false); final ClassGraph cg = new ClassGraph(cg1, "from TransitionInstance bypassing -> *,tail,* to *"); List l; l = cg.gather(m,"from TransitionInstance via ->*,c,* to Literal"); System.out.println(l.size()); System.out.println(" done "); l = cg.gather(m,"from TransitionInstance via ->*,a,* to Literal"); System.out.println(l.size()); System.out.println(" done "); cg.traverse(m,"from TransitionInstance via Assignment to Star", new Visitor() { int c; public void start() { c = 0; } public void after(Assignment host) { System.out.println("count " + c); } public void before(Star host) { c++; System.out.print("* "); } public void finish() { System.out.println(" end of traversal"); } } ); Integer posCSI = (Integer) cg.traverse(m,"from TransitionInstance to ConstraintSatisfactionInst", new Visitor() { int c; public void start() { c = 0; } public void before(ConstraintSatisfactionInst host) { List l1 = cg.gather(host ,"from ConstraintSatisfactionInst to Neg"); if (l1.size() == 0) c++; System.out.println("CSI " + c); } public Object getReturnValue() { return new Integer(c); } }); System.out.println(posCSI+ " output "); m.display(); } }} } TransitionInstance { void display() to * (DisplayVisitor); } PROGRAM INPUT: =========================================================== // this is an artificial transition sequence // 1* !2 3* 4 || 22(1 !2 3) by UnitPropagation 1* !2 3* 4 5 || 22( 1 2 3) by Learn 1* !2 3* 4 5 6* || 22( 1 2 3) 169(3 4 5) by Learn 1* !2 3* 4 5 6* || 22( 1 2 3) 169(3 !4 5) 154(4 5 6) by UnitPropagation 1* !2 3* 4 5 6* 7 || 22( 1 2 3) 169(3 4 5) 154(4 5 6) PROGRAM OUTPUT: ============================================================== Reading project file program.prj... Running the test... UNKNOWN1 done UNKNOWN2 done UNKNOWN3 count UNKNOWN4 UNKNOWN5 count UNKNOWN6 UNKNOWN7 count UNKNOWN8 UNKNOWN9 count UNKNOWN10 UNKNOWN11 count UNKNOWN12 end of traversal CSI UNKNOWN13 CSI UNKNOWN14 CSI UNKNOWN15 CSI UNKNOWN16 CSI UNKNOWN17 UNKNOWN18 output : TransitionInstance ( : BinaryS ( : Assignment ( : OptDecisionLiteral_List { : Nonempty_OptDecisionLiteral_List ( : OptDecisionLiteral ( : UNKNOWN19 ( : VarNumber ( : Number "1" ) ) : UNKNOWN21 ( ) ) : Nonempty_OptDecisionLiteral_List ( : OptDecisionLiteral ( : UNKNOWN22 ( : VarNumber ( : Number "2" ) ) ) : Nonempty_OptDecisionLiteral_List ( : OptDecisionLiteral ( : UNKNOWN23 ( : VarNumber ( : Number "3" ) ) : Star ( ) ) : Nonempty_OptDecisionLiteral_List ( : OptDecisionLiteral ( : Pos ( : VarNumber ( : Number "UNKNOWN24" ) ) ) ) ) ) ) } ) : ConstraintSatisfactionInst ( : Constraint_List { : Nonempty_Constraint_List ( : Constraint ( : RelationName ( : Number "UNKNOWN25" ) TRUNCATED