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.