INSTRUCTIONS: Write your name and SID at the top of every page. Write your answers on the exam sheet in the white space below the questions. When you finish, show your id when you turn in your exam. Item Question Maximum Points Actual Points 1 1a 2.0 2 1b 2.0 3 1c 1.0 4 2 5.0 5 3a 5.0 6 3b 5.0 7 3c 5.0 8 3d 5.0 9 4a 5.0 10 4b 5.0 11 4c 5.0 12 4d 5.0 13 5a 5.0 14 5b 5.0 15 6a 5.0 16 6b 5.0 17 7a 5.0 18 7b 5.0 19 8 5.0 20 9a 5.0 21 9b 5.0 22 9c 5.0 TOTAL 100.0 NAME 2 PSU Login ID 1. In uninformed search, the frontier stores states that are available for expanding during search. In breadth first search (BFS), consider the strategy for adding to and expanding the frontier. a. (2 points) Indicate how BFS starts (how the frontier is initialized). Write your answer below. b. (2 points) Indicate how nodes are added and expanded. Write your answer below. c. (1 point) Indicate how it terminates. Write your answer below. 2. (5 points) The tree below is a breadth first search tree, showing more of the search space than is needed: the goal node is the one labelled I (circled in a thick black line). Indicate in the table below the succession of frontiers through this tree, using the indicated format: place the next node that is expanded in column 1, and place the new frontier in column 2. Add rows as needed. For completeness and ease of grading, the final row should show the goal state in column 1 and the word “Goal” in column 2. NAME 3 PSU Login ID Node to expand New List of Frontier Nodes A BCD 3. A good search heuristic can reduce the search complexity. a. (5 points) Explain a strategy to find a good heuristic. Write your answer below. Find the cost of a solution to a relaxed version of the search problem. b. (5 points) Give one of the two example heuristics for the 8-puzzle problem given in class. Write your answer below. Two heuristics discussed in class are OOP (number of out-of-place tiles) and MD (manhattan distance). c. (5 point) Explain how your answer to 3b is consistent with the strategy. In the 8-puzzle problem, a tile can move from A to B only if B is empty and B is adjacent to A. OOP relaxes the problem to allow a move in one step from A to any location B. The number of OOP tiles will never over-estimate the cost to the goal. MD is the number of moves from A to B, always moving to an adjacent square, not necessarily an empty one. MD will also never overestimate the cost to the goal. d. (5 points): Give the second example for the 8-puzzle problem, and explain which is a better heuristic and why. NAME 4 PSU Login ID MD is better because it is more accurate; MD ≥ OOP and MD ≤ true cost. 4. Hill-climbing is a search method that evaluates the next move in a search, and is useful when there is no way to specify the entire state space for a search problem. It always moves to a nearby state if the successor state has a better evaluation than the current state. It is very efficient because there is no need to store any data other than the current state and the evaluations of nearby states. The drawback is that it can reach a local maximum that is far from the global maximum. Hill climbing with random restart is guaranteed to succeed, given unlimited restarts, but is therefore very inefficient in the worst case. a. (5 points) What is the search method studied in class that combines the efficiency of hill-climbing with the completeness of random restart? Write your answer below. Simulated annealing b. (5 points) What is the critical new parameter of this method called? Write your answer below. Temperature c. (5 points) Describe how this parameter is used during the search. The temperature parameter T controls whether a new state will be selected as successor, even if it has a worse evaluation than the current state. T starts out high, and is lowered gradually. The acceptance probability to choose a successor state is always greater than 1 if the new state is better, and is always positive. It decreases as T decreases, and as new states become increasingly worse. d. (5 points) Explain how this parameter makes the search behavior different early in the search versus late in the search. The consequence of starting with a high T that is lowered gradually is that early in the search, it is more likely that a worse state will be moved to, allowing escape from local maxima. As the search continues, the probability of accepting a worse state decreases. If T is lowered slowly enough, simulated annealing is Complete. NAME 5 PSU Login ID 5. Constraint Satisfaction Problems: A CSP has a finite set of variables Xi, Xi+1, . . . Xn, a non-empty domain for each variable, and constraints that limit the values that variables can take. In this problem, you will draw a constraint graph (part a), and apply arc consistency (part b). This means you first check the consistency of every arc Xi-Xj after you make an assignment to Xi, then for every Xj that loses a value, recheck its arcs (other than Xi-Xj). You just started working for a map maker who gave you a practice exercise to color in the seven western states of Utah, Arizona, Nevada, Idaho, Wyoming, Colorado and New Mexico. No two states sharing a border (a measurable edge) can be the same color. The three colors you have to chose from are red, blue and green (RBG). Ignore all the other states in the figure that have grey shading. a. (5 points) At the top of the next page, draw the constraint graph for the above map coloring problem. b. (5 points) Apply arc consistency to this problem. The provided table below shows all 7 variables (U.S. states) in the columns, and the first row shows the initial domain for each state (RGB). Using this table, first add a row where you make an initial assignment of red (R), and eliminate values that are inconsistent with this assignment as follows: i. add a new row and assign a color to the most constraining state Si (if multiple states are tied for most constraining, select the state that is leftmost in the table); ii. circle the value you assigned; iii. in the last column list all the arcs Si-Sj that need to be checked for consistency given the assignment to Si; iv. enter the new domains for the variables Sj connected to Si to make them consistent. v. Having added one row for an assignment to one variable, and all the arcs involving that one variable, now do further consistency checking as NAME 6 PSU Login ID follows: add a row to show the new domains for any states that needed consistency checking due to an Sj from the previous row whose domain was reduced; vi. list the relevant arcs Sj-Sk in the ARCS column. vii. Repeat steps i through vi until you reach a solution, or find there is no solution. At row 3, the next most constraining states after UT are all the others but NM, so the tables show assignments for picking NV first, ID first, etc Pick NV’s color in row 3 = B NV ID WY CO AZ UT NM ARCS # RBG RBG RBG RBG RBG RBG RBG 1 BG BG BG BG BG R RBG UT-AZ,UT-NV,UT-ID,UT-WY,UT-C O 2 BG BG BG BG BG R RBG No change 3 B G BG BG G R RBG NV-ID, NV-AZ (tied NV, ID, WY, CO, AZ) 4 B G B G G R R ID-WY, WY-CO, NM-WY, NM-AZ Pick NV’s color in row 3 = G NV ID WY CO AZ UT NM ARCS # RBG RBG RBG RBG RBG RBG RBG 1 BG BG BG BG BG R RBG UT-AZ,UT-NV,UT-ID,UT-WY,UT-C O 2 BG BG BG BG BG R RBG No change NAME 7 PSU Login ID 3 G B BG BG G R RBG NV-ID, NV-AZ (tied NV, ID, WY, CO, AZ) 4 G B G B B R R ID-WY, WY-CO, NM-WY, NM-AZ 6. The syntax of first order logic (FOL) differs from predicate logic in that along with constants (Mary, William) and connectives ( ¬ ⋁ ⋀ ⇒ ⇔), FOL syntax has predicates, functions, variables, equality and the two quantifiers (∀ ∃ ). a. (5 points) Translate the following English sentences into FOL. Every dog barks. ∀x dog(x) ⇒ bark(x) Some birds speak. ∃x bird(x) ⋀ speak(x) b. (5 points) Translate the following FOL expressions into English. ∀x ∃y person(x) ⋀ person(y) ⋀ admire(x, y) Everyone admires someone. ∃x ∀y mountain(x) ⋀ person(y) ⋀ ¬ climb(y, x) There is a mountain no one has climbed. 7. For any finite, discrete events a and b, their probabilities are in the range [0,1]: 0 ≤ P(a) ≤ 1 and similarly, 0 ≤ P(b) ≤ 1 , a. (5 points) Which of the following is true? i. P(a ⋀ b) = P(a) + P(b) − P(a ⋁ b) ii. P(a ⋁ b) = P(a) + P(b) − P(a ⋀ b) b. (5 points) If P(a) = 0.6 and P(b) = 0.1 , which of the following statements about P(a ⋀ b) cannot be true: i. P(a ⋀ b) = 0 ii. P(a ⋀ b) < 0.1 iii. P(a ⋀ b) < 0.6 iv. P(a ⋀ b) > 0.1 NAME 8 PSU Login ID A C P(B) T T T F P(A) F T P(C) F F D P(E) TF 8. (5 points) In a Belief Net, each node is a random variable, and the directed edges represent conditional dependence of children on their parents, and conditional independence of all other random variables. In the above Belief Net composed of 5 random variables, each is binary, meaning it takes on the value True or False. E is conditionally dependent on D, D is conditionally dependent on A and on B and on C, and B is conditionally dependent on C and A. Next to each node, show its CPT (conditional probability table) that specifies all the distinct possibilities for each child node conditioned on its parents. That is, ignoring the actually probability values for each possible combination of parents’ values, indicate the columns and rows needed for each node’s CPT, by showing the combination of values for each row. NAME 9 PSU Login ID 9. CKY parsing requires a binarized grammar, meaning a context free grammar in Chomsky Normal Form. a. (5 points) A context free grammar is a 4-tuple (N, Σ , R, S). Define each member of this tuple. Use the space below. N a set of non terminal symbols Σ a set of terminal symbols (disjoint from N) R rewrite or production rules A → β where β is a string from (N ⋃ Σ )* S a start symbol b. (5 points) CKY parsing (short for Cocke-Kasami-Younger) is an example of a dynamic programming algorithm that uses a chart. Explain the constraint that all grammar rules must meet to count as “binarized” and why CKY parsing requires the grammar to be in this form. In a binarized CFG, all rewrite or production rules are one of the following: a) a non-terminal symbol on the LHS and a single terminal on the right hand side b) a non-terminal symbol on the LHS and exactly two non-terminal symbols on the right hand side NAME 10 PSU Login IDc. (5 points) Given the sentence “The winger passed the striker kicking the ball” draw a CKY chart for parsing this sentence in its initial form showing the upper diagonal, the indices on the horizontal and vertical dimensions for keeping track of substrings, and fill in three cells (upper left region) that show Terminal → Non-terminal rules applied to the first two words “the” and “winger,” and the application of a rule of the form Terminal Non-terminal1, Non-terminal2 → to the entire phrase “the winger.” (Note: “winger” and “striker” are soccer positions.)