CS 540-1: Introduction to Artificial IntelligenceMidterm Exam: 7:15-9:15pm, March 22, 1999CLOSED BOOK(one page of notes and a calculator allowed)Write your answers on these pages and show your work. If you feel that a question is not fullyspecified, state any assumptions you need to make in order to solve the problem. You may usethe backs of these sheets for scratch work.Write your name on this and all other pages of this exam. Make sure your exam contains sixproblems.Name ________________________________________________Student ID ________________________________________________Problem Score Max Score1 _____ 252 _____ 253 _____ 84 _____ 205 _____ 106 _____ 12Total _____ 100(over)CS 540-1 2 Name ____________________PROBLEM 1 - Decision Trees (25 points)Assume you are given the following features with the possible values shown.F1 ∈ {A, B, C}F2 ∈ {D, E}F3 ∈ {G, H, I}F4 ∈ {J, K}a) Consider the following training examples.ex1 F1 = A F2 = E F3 = H F4 = J category = +ex2 F1 = A F2 = E F3 = G F4 = K category = -ex3 F1 = A F2 = D F3 = G F4 = J category = +ex4 F1 = B F2 = D F3 = G F4 = J category = +ex5 F1 = B F2 = E F3 = H F4 = J category = +ex6 F1 = B F2 = E F3 = H F4 = K category = -ex7 F1 = C F2 = D F3 = H F4 = K category = -ex8 F1 = C F2 = D F3 = G F4 = J category = -i. What score would the information gain formula assign to each of the features?Be sure to show all your work.(Some calculations that might be of use: I(x,y)=I(y,x), I(1,0)=0, I(1/2,1/2)=1, I(1/3,2/3)=0.92,I(1/4,3/4)=0.81, I(1/5,4/5)=0.72, I(1/6,5/6)=0.65, I(1/7,6/7)=0.59, I(1/8,7/8)=0.54)ii. Which feature would be chosen as the root? _________(Break any ties in favor of F1 over F2 over F3 over F4, and ’+’ over ’-’.)(over)CS 540-1 3 Name ____________________iii. Show the next interior node, if any, that ID3 would select. Again, be sure to show allyour work (use the back of this or the previous sheet if necessary).Note that, to avoid spending excessive time, you are only being asked to create at mostthe first two (2) interior nodes. Do create as many the leaf nodes as possible, givenyour choice of interior nodes.b) Imagine that we used in our training examples a discrete-valued feature that had a uniquevalue for each example, such as including in examples describing medical patients, eachpatient’s social-security number. (Notice that we are not treating this as a continuously-valuedfeature, but just as a discrete-valued feature with a very large number of possible values.)What would be the information gain of such a feature? Briefly discuss the implications of youranswer.(over)CS 540-1 4 Name ____________________PROBLEM 2 - Search Strategies (25 points)a) Assume you have the following search graph, where S is the start node and G1 and G2 aregoal nodes. Arcs are labeled with the cost of traversing them and the estimated cost to a goal isreported inside nodes.SABDCG2G14E1126KEY261007204571 5874745Estimated cost tonearest goal is XCost of traversingthis arc is YY XFor each of the search strategies listed below, indicate which goal state is reached (if any) andlist, in order, all the states expanded. (Recall that a state is expanded when it is removed fromthe OPEN list.) When all else is equal, nodes should be expanded in alphabetical order.Breadth-FirstGoal state reached: _____ States expanded: ____________________________________Iterative DeepeningGoal state reached: _____ States expanded: ____________________________________Hill Climbing (using the h function only)Goal state reached: _____ States expanded: ____________________________________A*Goal state reached: _____ States expanded: ____________________________________(over)CS 540-1 5 Name ____________________b) Imagine that the simulated annealing algorithm is at node A and has randomly chosen nodeD is the candidate next state. Assuming the temperature equals 5, what is the probability thatnode D will be accepted as the next state?Repeat the above, but this time assume node E is the candidate next state.PROBLEM 3 - Game Playing (8 points)a) Apply the minimax algorithm to the partial game tree below, where it is the minimizer’s turnto play. The values estimated by the static-board evaluator (SBE) are indicated in the leaf nodes.Write the estimated values of the intermediate nodes inside their circles, and indicate the propermove of the minimizer by circling one of the root’s outgoing arcs.11 12minimizermaximizer9 -7 4 -8 -9 -2b) Indicate, by crossing out, one (1) unnecessary call to the static-board evaluator. Explain whythis call to the SBE is unnecessary.(over)CS 540-1 6 Name ____________________PROBLEM 4 - Propositional Logic (20 points)a) Given the interpretation P=true and Q=false, determine the truth value of the following:[(P ∨ Q) ⇒ Q] <=> [P ∧ ¬ Q]b) Using a truth table, show that the following is valid (i.e., is true for all possibleinterpretations for P and Q).(P ∧ Q) <=> ¬(¬ P ∨ ¬ Q)(over)CS 540-1 7 Name ____________________c) Given the well-formed formulae (wff’s) below, show that (S ∨ R) logically follows (don’t domore than 10 deductive steps):WFF Justificationhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh1 P given2 (Q ∧ W) given3 (P ∧ Q) ⇒ (S ∨ Z) given4 (A ∨ R ∨ ¬ Z) given5 ¬ A given6789101112131415(over)CS 540-1 8 Name ____________________PROBLEM 5 - Miscellaneous Short Answers (10 points)Provide brief answers to the following questions.hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhA. Why do we use test sets in machine learning? What is wrong with using the same subset ofdata for one’s pruning set and test set in ID3?hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhB. If a solution of length N is known to exist, is beam-search with beam-width=2N guaranteedto find it?hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhC. Express the following sentence in predicate calculus:Every red ball is made of rubber.(over)CS 540-1 9 Name ____________________hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhThe End!CS 540-1 10 Name ____________________Problem 6 - Information Theory and Expected Values (12 points)Assume that in your morning email each day you get a message from Amazing.com. The lastline of each message always says how many free dollars you have for use at their site that day.You’re told that 95% of the time, you’ll get $1 and 5% of the time