Midterm CS 4500
Karl Lieberherr					Fall 2009
=========================================================
Tuesday, Nov. 3, 2009

Open book and open notes.

Consider the following NEW REQUIREMENT:

We introduce a new kind of ALL challenge, called
a midterm challenge.

A midterm challenge d uses 2 relations (equality and inequality)
and is described by 
d=(equality c1 c2 c3 r inequality d1 d2 s price p), 
where c1,c2,c3,r,d1,d2,s are integers describing the two relations
and p is a price in the interval [0,1] of real numbers.

In the following, x,y,z assume values in the set {0,1},
i.e., the integers 0 and 1 only.
Note that we use a prefix notation to make 
writing the grammar easier.

Problems use constraints of the following two forms:

weight w1 = c1*x + c2*y + c3*z r
  (meaning c1*x + c2*y + c3*z = r; w1 is the weight.)
weight w2 >= d1*x + d2*y s
  (meaning d1*x + d2*y  >= s; w2 is the weight.)

w1, w2 are integers (constraint weights)
* is integer multiplication
+ is integer addition
>= is greater or equal
=  is equality

An example of a midterm challenge is: 
ch1=(equality 1 1 1 2 inequality 1 1 1  price 0.7)

Example of a problem for challenge ch1:

weight 5 = 1*x1 + 1*x2 + 1*x3 2
  // the weight is 5.
  // the first constraint means that exactly 2 of the 3 variables
  // must be 1.
weight 9 = 1*x1 + 1*x2 + 1*x4 2
weight 4 >= 1*x2 + 1*x3  1
  // the weight is 4
  // this constraint says that at least one variable is 1.
weight 3 >= 1*x3 + 1*x4  1
weight 1 >= 1*x2 + 1*x4  1

Questions:
First answer questions 1-3. 

1. 15 points
   Compute the break-even price of midterm challenge ch1.
   ch1=(equality 1 1 1 2 inequality 1 1 1  price 0.7)
   Show the details of your computation.
2. 10 points
   If an agent accepts your challenge ch1, what is the problem SS that
   you would provide to the agent. Assume that you are only allowed to use
   5 variables. What is the best assignment that can be achieved for SS? 
3. 15 points
   Design a class dictionary (or a grammar and object-oriented design)
   for the above challenge language and problem language.
4. 15 points 
   Conceptually describe how this new kind of challenge fits into
   FAST PITCH SOFTBALL.  Does the requirement change affect
   the game significantly? Justify your answer.
5. 20 points
   How does this requirements change affect
   your agent (for ALL challenges only).
   Describe how you would update or add key components to your agent.
   How would you incorporate the new kind of challenge into your agent?
   List tasks for the sprint backlog to implement midterm challenges.