CS343: Midterm ExamMarch 12, 2009NAME:1. (25 points) Consider the following search problem. Assume a state is represented as an integer,that the initial state is the number 1, and that the two successors of a state n are the states2n and 2n + 1 (in this order). For example, the successors of 1 are 2 and 3, the successors of2 are 4 and 5, the successors of 3 are 6 and 7, etc. Assume the goal state is the number 12.Consider the following heuristics for evaluating the state n where the goal state is g• h1(n) = |n − g| (the absolute value of the difference)• h2(n) = (g − n) if n ≤ g and h2(n) = ∞ otherwise (n > g)Below and on the following blank page, show the search trees generated for each of thefollowing strategies for the initial state 1 and the goal state 12, numbering the nodes in theorder expanded. Assume goal states are detected as soon as they are generated instead ofwaiting until they are expanded.(a) Depth-first search(b) Breadth-first search(c) Best-first with heuristic h1(d) Best-first with heuristic h2(e) Hill-climbing with heuristic h1If any of these strategies get lost on an infinite path and never find the goal, simply show thesearch tree for a few steps and then say “FAILS.”1Search Trees for Problem 122. (15 points) Consider the following simple game tree showing the utility (or heuristic evalua-tion) of each of the leaves. Assume alpha-beta search is used to pick the best move for Maxat the top level and that siblings are explored in left to right order. Circle each leaf nodethat is actually evaluated and show each updated bound and exact value established for theutility of any intermediate nodes. Number each step in order. What is the best move forMax (left or right)?33. (16 points) Represent the following in first-order logic. Make sure to use a reasonable setof primitive predicates that capture the basic concepts. Explain any predicates and theirarguments that are not obvious.Every company layed-off at least two employees and at least one of them hated their boss.There is a town in a state that borders Texas in which all residents were killed by someonewho sells an illegal drug. (Note: Assume each person may have been killed by a differentdrug dealer but that they all sell the same illegal drug)44. (23 points) Given the following KB in first order logic“For every test in a CS course, at least one person fails.”∀x∀y(CScourse(x) ∧ Test(y,x) ⇒ ∃z Fail(z, y))“Everyone passes an easy test in a course.”∀y((∃x Test(y,x)) ∧ Easy(y) ⇒ ∀z Pass(z,y))“No one can both pass and fail the same test.”¬∃x∃y(Pass(x,y) ∧ Fail(x,y))“Class1 had an easy test.”Test(Exam1,Class1)Easy(Exam1)Use resolution to prove:“Class1 is not a CS course.”¬CScourse(Class1)Show the conversion to clause form and clearly indicate each resolution used in the proof.The straightforward proof contains 6 resolutions.55. (21 points) Provide short answers (1-3 sentences) for each of the following questions:What are the four primary criteria used to evaluate search algorithms (i.e. fundamental prop-erties that you should ask about any method)?What is the worst aspect of breadth-first search compared to other uninformed search strate-gies? Be specific.Describe the evaluation function used to sort the queue in A* search? Be specific and defineany terms that you use.(Extra credit) What was Alan Turing’s favorite Disney movie?6What is the worst case time complexity of all known algorithms for determining whether ornot a sentence in propositional logic is a tautology. Assume the sentence contains n proposi-tional symbols.What is the primary advantage of backward chaining over forward chaining for most inferenceproblems. Be specific.Explain what is meant by the statement that resolution theorem proving in first-order logicis semi-decidable.Name and clearly define the unusual form of negation used in