Midterm CS 4500 Fall 2009 ---------------------------------------------------------- Question 1 (15 points) and 2 (10 points): 104 is the relation number for x1 + x2 + x3 = 2 238 is the relation number for x1 + x2 >= 1 (x3 is a don't care) Remember to reverse the order of the variables for our standard encoding. Note that 104 implies 238. Therefore we forget about 238 both for the break-even calculation and the provided problem. 4/9 is break-even price for 104 3 * p^2 * (1-p) b_max = 2/3 Symmetric formula: x1 + x2 + x3 = 2 x1 + x2 + + x4 x1 + x3 + x4 x2 + x3 + x4 x1 + x2 + x5 x1 + x3 + x5 x2 + x3 + x5 x1 + x4 + x5 x2 + x4 + x5 x3 + x4 + x5 = 2 k = number of variables set to 1 k = 2: 3/10 k = 3: 6/10 k = 4: 6/10 k = 5: 0 Now add: x1 + x2 >= 1 x1 + x3 x2 + x3 x1 + x4 x2 + x4 x3 + x4 x1 + + x5 x2 + x5 x3 + x5 x4 + x5 >= 1 k = 3: 9/10 k = 4: 10/10 Only makes it easier! Because of implication. Question 3: (15 points) ===================================== nogen List(X) = Cons(X) | Empty(X). nogen Cons(X) = X List(X). nogen Empty(X) = . Both = "cl" ChallengeLanguage "pl" ProblemInstance EOF. ChallengeLanguage = "(" Equality Inequality "price"

Price ")". Equality = "equality" int int int int. Inequality = "inequality" int int int. Price = double. ProblemInstance = List(Constraint). Constraint = Weight Body. Weight = "weight" int. Body = Eq | Ineq int. Eq = "=" VC "+" VC "+" VC. Ineq = ">=" VC "+" VC . VC = int "*" Var. Var = ident. Question 4: ---------------------------------------------------------------------- A midterm challenge ch is translated to a Fast Pitch Softball/ALL challenge ((R1,R2), price), where R1 and R2 can be easily computed from ch. Midterm challenges are in this sense a special case of Fast Pitch Softball/ALL challenges. Similar to the way we reduced Slow Pitch Softball to TBall. Given a midterm challenge we translate it into two relation numbers as follows: c1*x + c2*y + c3*z = r has the following truth table z y x value 0 0 0 0=r 0 0 1 c1=r 0 1 0 c2=r 0 1 1 c1+c2=r 1 0 0 c3=r 1 0 1 c1+c3=r 1 1 0 c2+c3=r 1 1 1 c1+c2+c3=r which in turn defines a relation number. d1*x + d2*y >= s has the following truth table z y x 0 0 0 0>=s 0 0 1 d1>=s 0 1 0 d2>=s 0 1 1 d1+d2>=s 1 0 0 0>=s 1 0 1 d1>=s 1 1 0 d2>=s 1 1 1 d1+d2>=s which in turn defines a relation number. Short answer: Midterm challenges have a different syntax than Fast Pitch Softball, but it has the same semantics. Because the variables in the new challenge are only 0,1, we can find the two corresponding relation numbers. It would affect parsing, but not the game logic. Question 5: (20 points) Tasks: Update parser to recognize new formats. Accept: Translate new challenge to old challenge and use current Accept. Solve: Translate new problem to old problem and use current Solve. Offer: Create a new challenge. To compute its appropriate price, translate new challenge to old challenge and compute its price using current break-even method. Provide: Use current Provide to create old problems and translate to new problems. Question to resolve: When are two midterm challenges the same? Add unit tests for translation.