Name: CIS 521
Page 1 of 7
THE UNIVERSITY OF PENNSYLVANIA
SAMPLE EXAM – Given in
Fall, 2015
Points Possible: 100
POINT COUNTS
ACCURATE
CIS 521
INTRODUCTION TO ARTIFICIAL INTELLIGENCE
Midterm I
(Time allowed: 80 minutes)
Section Points Max
1 True/False Multiple Choice 20
2 Search 20
3 Heuristics 20
4 Adversarial search 10
5 Constraint Satisfaction 15
6 Naïve Bayes NOT
APPLICABLE
15
TOTAL 100
Name: CIS 521
Page 2 of 7
Question 1. [20] True-False & Multiple Choice
[All questions worth 2 points.]
a) In Python, what does the last command in this sequence print?
> x = [[(x, y) for x in 1,2,3] for y in 1,2,3]
> len(x)
(a) 1
(b) 3
(c) 6
(d) 9
b) TRUE or FALSE: Depth-first search is complete.
c) TRUE or FALSE: Depth-first search has, in general, much lower space complexity than
iterative deepening.
d) TRUE or FALSE: In estimating the travel distance between two locations, Euclidean
distance is a consistent and admissible heuristic.
e) TRUE or FALSE: A* search uses heuristics to prune the search space so that the use of
space is effectively O(bd).
f) TRUE or FALSE: Iterative deepening is complete in that it is guaranteed to halt if there is a
solution path to the goal.
g) TRUE or FALSE: Uniform-cost search is a special case of A* search.
Name: CIS 521
Page 3 of 7
h) Which of the following is true?
a. All admissible heuristics are consistent
b. All consistent heuristics are admissible
c. Both of the above
d. Neither of the above
i) Given the joint probabilities in Table 1 below, what is the probability of having a cavity if
there’s no toothache?
Table 1: Joint probabilities
(a) 0.12
(b) 0.4
(c) 0.4/(0.12 + 0.4)
(d) none of the above
j) What assumption is made in deriving the Naive Bayes model? ( ic is the class random
variable and ix is the feature random variable; note that there are N classes and also N
features)
(a) P(x1 . . . xN | ci ) = P(x1 | ci ) P(x2 | ci ) . . . P(xN | ci )
(b) P(x1 . . . xN, c1 . . . cN) = P(x1, c1) . . . P(xN , cN )
(c) P(c1 . . . cN | xi ) = P(c1|xi ) P(c2|xi ) … P(cN |xi )
(d) P(x1 . . . xN, c1 . . . cN) = P(c1) P(x1|c1)P (c2 |x1, c1 ) . . . P(xN |x1 . . . xN −1, c1 . . . cN )
(e) None of the above.
toothache ¬ toothache
cavity 0.12 0.4
¬ cavity 0.1 0.38
Name: CIS 521
Page 4 of 7
Question 2. [20] Search
Consider the following search space where we want to find a path from the start state S to
the goal state G. The table shows three different heuristic functions h1, h2, and h3.
Node h1 h2 h3
S 0 5 6
A 0 3 5
B 0 4 2
C 0 2 5
D 0 5 3
G 0 0 0
a) [5] What solution path is found by Greedy Best-first search using h2? Break ties
alphabetically.
b) [15] Give the three solution paths found by algorithm A* using each of the three
heuristic functions, respectively. Break ties alphabetically.
h1:
h2:
h3:
Name: CIS 521
Page 5 of 7
Question 3. [20] Heuristics
Consider the 8-puzzle consisting of a 3 x 3 board with eight tiles numbered 1 through 8.
The goal is to move the tiles from a start configuration to a goal configuration, where a
move consists of a horizontal or vertical move of a tile into an adjacent position where
there is no tile. Each move has cost 1.
(a) [10] Is the heuristic function defined by h ¦Di di admissible, where di is the
i 1
number of vertical plus the number of horizontal moves of tile i from its
current position to its goal position assuming there are no other tiles on the
board, and 0 ≤ ai ≤ 1 is a constant weight associated with tile i? Explain
briefly why or why not.
(b) [10] Given two arbitrary admissible heuristics, h1 and h2, which composite
heuristic of the following three is best to use?
a) max(h1, h2)
b) (h1 + h2)/2
c) min(h1, h2)
Briefly explain why.
Name: CIS 521
Page 6 of 7
Question 4. [10] Adversarial Search
The following tree represents all possible outcomes of a hypothetical zero-sum game:
2
α: β:
1
α:−∞ β:∞
5
α: β:
3
α: β:
4
α: β:
6
α: β:
7
α: β:
1 4 10 3 7
2 9 8 4
This tree is from the perspective of the MAX player; MAX nodes are represented by squares and
MIN nodes by circles. The leaves of the tree represent the value of the game for the MAX player.
The index of each node indicates the order in which they are considered by the Minimax and α-β
pruning algorithms.
D) [5 point] What are the “back-up” values of each node in tree using the Mini-max strategy? (The lists are
ordered by the node numbers, 1 to 7.)
(a) 3, 3, 1, 3, 4, 2, 4
(b) 4, 4, 4, 10, 2, 2, 9
(c) 10, 10, 4, 10, 9, 2, 9
(d) 1, 1, 1, 3, 2, 2, 4
(e) None of the above
E) [5 point] Run the α-β pruning algorithm and list each leaf (by its value) and node (by its index) that
would NOT be considered by the α-β pruning algorithm. (Assume that leaves are considered in left-to-
right order.)
(a) Nodes: 7; Leaves: 3, 7, 9, 8 ,4
(b) Nodes: 5,6,7; Leaves: 2, 9, 8, 4
(c) Nodes: 4, 7; Leaves: 10, 3, 7, 9, 8, 4
(d) Nodes: None; Leaves: None
(e) None of the above
Name: CIS 521
Page 7 of 7
Question 5. [15] Constraint Satisfaction
Consider the problem of assigning colors to the five squares on the board below such that horizontally
adjacent and vertically adjacent squares do not have the same color. Assume there are two possible colors,
red (R) and black (B). Formulated as a constraint satisfaction problem, there are five variables (the
squares) with two possible values (R, B) as the domain of each variable.
a) [5] If initially every variable has both possible values and we then assign variable 1 to have value
R, what values remain for each cell after running the Forward Checking algorithm?
1:
2:
3:
4:
5:
b) [5] If initially every variable has both possible values, what values remain for each cell after
running AC-3?
1:
2:
3:
4:
5:
c) [5] If initially every variable has both possible values and we then assign variable 5 to have value
B, what values remain for each cell after running AC-3?
1:
2:
3:
4:
5: