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.