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) = <first> X <rest> List(X).
nogen Empty(X) = .

Both = "cl" <cl> ChallengeLanguage "pl" <pl> ProblemInstance EOF. 

ChallengeLanguage =
"(" <e> Equality <ie> Inequality "price" <p> Price ")".
Equality = "equality" <c1> int <c2> int <c3> int <r> int.
Inequality = "inequality" <d1> int <d2> int <s> int.
Price = <v> double.

ProblemInstance = <constraints> List(Constraint).
Constraint = <w> Weight <b> Body.
Weight = "weight" <v> int.
Body = Eq | Ineq <rhs> int.
Eq = "=" <vc1> VC "+" <vc2> VC "+" <vc3> VC. 
Ineq = ">=" <vc1> VC "+" <vc2> VC . 
VC = <c> int "*" <v> Var.
Var = <v> 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.