Pg 1/7
Name: _______________________


CS 331 Midterm
Spring 2019

You have 50 minutes to complete this midterm. You are only allowed to use your
textbook, your notes, your assignments and solutions to those assignments during this
midterm. If you find that you are spending a large amount of time on a difficult question,
skip it and return to it when you’ve finished some of the easier questions. Total marks
for this midterm is 43.




Section Marks
Agents

/ 8
Search

/ 11
Games

/ 12
Logic / 12

Total / 43













Pg 2/7
Section I: Agents (8 points)
1. Consider an agent solving a Sudoku puzzle.

For each part below, circle the choice which best describes the environment for this
agent:

a) Fully observable or Partially observable [1 point]



b) Deterministic or Stochastic [1 point]



c) Episodic or Sequential [1 point]



d) Static or Dynamic [1 point]



e) Discrete or Continuous [1 point]



f) Single agent or Multi-agent [1 point]




2. What type of agent is a Sudoku solver? Choose from simple reflex agent, model-based
reflex agent, goal-based agent and utility-based agent. Give a one or two sentence
justification of your answer. [2 points]

Could argue for simple reflex, reacting to the state of the board at a given time and filling
in the next number.

Could argue for goal-based, reasoning about a sequence of actions to fill in the board.







Pg 3/7
II. Search [11 points]
3. The following questions deal with the search algorithms you implemented in
Programming Assignment #1.

a) If breadth-first search (BFS) is implemented correctly, is it possible for depth-first
search (DFS) to find an optimal solution path while expanding fewer nodes than BFS?
Why or why not? [2 points]

Yes, DFS could get “lucky” and find the optimal goal on the first depth-first pass.






b) Suppose we use A* tree search to solve the Wolves and Chickens problem from the
first programming assignment with 3 wolves and 3 chickens. If we set ℎ() = 1 for all
nodes (except goal nodes, which for which we set ℎ() = 0), does the algorithm find an
optimal solution? Why or why not? [2 points]


The heuristic is admissible, so optimality is guaranteed. (This is a bad heuristic because it
is uninformative, but the negative impact on the algorithm will be in efficiency instead of
optimality.)








c) Suppose you implement two version of A-star search: one with heuristic h1 and the
other using heuristic h2. Both heuristics are admissible, but for all nodes n, h2(n) > h1(n).
Which version expands more nodes?

h1(n) expands more nodes.









Pg 4/7
4. The following questions deal with local search algorithms.

a) Name one local search algorithm that is not optimal (i.e., it may find local instead of
global optima). Describe how adding an element of stochasticity can improve the
algorithm. [3 points]

Several answers are possible. For example, hill climbing is not optimal, but random
restarts can improve performance.









b) Suppose you are considering two options for solving a search problem: (i) A-star
search with a good heuristic function, and (ii) a local search algorithm (e.g., simulated
annealing). When would you prefer using (ii) over (i)? [2 points]

Factors: substantial memory limitations to deal with, an approximate (good but not
necessarily optimal) solution would suffice.























Pg 5/7
III. Games [12 points]
5. Below is a portion of a game tree. What is the expectiminimax value at the root node?
Show your work. [6 points]


6. Suppose that you are running the minimax algorithm with alpha-beta pruning on a
game tree. You have come to a subtree, shown below, and the current values of alpha and
beta are -4 and 8, respectively. Which branches (if any) are pruned in this subtree?
Indicate your answer with Xs and show work for partial credit. [6 points]








Pg 6/7
IV. Propositional Logic [12 points]
7. Is the following sentence valid, unsatisfiable, or neither? Justify your answer. [2
points]
(¬ ⇒ ) ∧ ¬ ∧ ¬

≡ ( ∨ ) ∧ ¬ ∧ ¬

We cannot have A or B true as well as both A and B false, so this is unsatisfiable.













8. Convert the following KB into Conjunctive Normal Form. [4 points]

¬( ∧ ) ⇒
¬( ∧ )

∨
∨
¬ ∨ ¬
















Pg 7/7
9. Use the resolution algorithm to determine whether the following KB entails . [6
points]
1. ∨
2. ¬ ∨
3. ∨ ¬ ∨
4.


5. ¬
6. ∨ ¬ (5 + 3)
7. (6 + 4)
8. ∨ (1 + 2)
9. ∨ (3 + 4)

Therefore, KB does not entail .