American University of Sharjah Instructor: Dr.
Michel Pasquier
College of Engineering Office: ESB-2057
Computer Science & Engineering Dept. Phone: 971-6-515-2883
P.O. Box 26666 E-mail: mpasquier@[Link]
Sharjah, UAE Semester: xxxx xxxx
CMP 333 ARTIFICAL INTELLIGENCE
MIDTERM EXAM PAPER – SAMPLE
Date: xxxx xx xxxxxxx xxxx (1 hour)
Student ID: _________________ Student Name: ___________________________
Instructions: Write both your name and ID above. Read the questions carefully; write
your answers clearly in the space provided. You can use draft paper, if necessary,
but it must be returned with this paper. This is a close book exam: neither books or
notes are allowed, nor is any communication with anyone but the examiner.
For Instructor’s Use Only:
Q1 Intelligent Agents [ch1,2] / 10
Q2 Problem Solving [ch3] / 10
Q3 Heuristic Search [ch4] / 14
Q4 Constraint Satisfaction [ch5] / 14
Q5 Adversarial Search [ch6] / 12
Q6 Logical Reasoning [ch7]
Q7 First-Order Logic [ch8]
Q8 Logical Inference [ch9]
Q9 Logical Programming [ch9x]
Q10 Probabilistic Reasoning [ch13]
Total: / 60
1/6
Question 1: Suppose you design an intelligent agent program to automatically identify and
delete incoming spam/junk e-mails from your mailbox based on their content.
(a) Explain exactly why a goal-based agent is not suitable in this case. (2 marks)
(b) Explain which of a simple reflex agent or a model-based reflex agent is best for
this application. Justify your choice precisely. (4 marks)
(c) Indicate which of the following properties the above task environment has, or
not. Justify your answers briefly but clearly. (4 marks)
observable:
deterministic:
episodic:
discrete:
static:
2/6
Question 2: (a) Give a standard problem formulation (not CSP)
i.e., states, initial state, goal state, operators, and path cost, 3 1
for the simplified Sudoku puzzle shown on the right. The 2 3
game is played on a grid of 4 blocks with 4 cells each. Some
of the cells are empty while some already contain a number. 3 2
The goal is to fill in the empty cells such that every row,
every column, and every 2×2 block contains each of the 4 3
numbers 1, 2, 3, 4 exactly once. (4 marks)
(b) Justify the branching factor and the solution depth for this problem. Explain
which search algorithm is most appropriate, based on problem characteristics,
and what kind of pruning is needed. Justify your answers precisely. (6 marks)
3/6
Question 3: Below is a country map that shows its 13 cities (A to M) and the roads that
connect them. The map shows inter-city distances while the table gives heuristic
values that are the estimated straight-line distances from each city to Mime (M).
Lipo
42 Mime
Alba 20 35
36 A B C D
14
40 Kran 40 30 29 33
36
Cinu 23
30 E F G H
Blis
Dorn Flak 32 31 27 32 34
27 30
26 25 19 Hust Jolt I J K L M
Gord 29 36 29 32 50 0
Elff 20 Inue
(a) Apply the A* search algorithm to work out the shortest route from Alba to
Mime. Show for each iteration the nodes in the fringe/frontier and their total f-
costs. (Do not draw the tree.) Assume that full pruning is applied. (7 marks)
(b) Comment on the efficiency of the search. Highlight the pros and cons of this
particular heuristics (examine the values closely). Give one benefit and one
drawback of changing the heuristic value of Flak from 27 to 100. (7 marks)
4/6
Question 4: Solve the cryptarithmetic puzzle on the right as a Constraint
T W O
Satisfaction Problem. Each letter must be uniquely replaced by a
+ T W O
digit so that the addition works as shown. You can assume that no
variable is 0, and therefore the only carry is F=1. = F O U R
Moreover, the constraint equations are as follows:
O¹R¹T¹U¹W O+O=R W+W=U T + T = 10 + O (since F=1)
(a) Justify the selected variable ordering [O, R, T, U, W] by showing exactly how
the Most Constraining Variable and Minimum-Remaining Value heuristics
apply to this problem. Lastly, show that 2 and 4 are the values to try first for the
letter O by applying the Least Constraining Value heuristics. (7 marks)
(b) Solve the puzzle by applying depth-first search with forward checking, using
the information from part (a). Assign variables in the given order and use LCV
for values (use ascending order if a tie). Fill the table below, showing at each
step the selected variable and value, and the resulting domains. (7 marks)
O R T U W
step 2,4 2-9 2-9 2-9 2-9
5/6
Question 5: Consider the game tree below, where each level shows the possible Max/Min
moves and the values of the heuristic evaluation function are given at the leaves.
(a) Write on the game tree the minimax value of each node A to L. Identify and
highlight accordingly the best strategy for both players. (3 marks)
Max A
B C D E
Min
F G H I J K L
Max
M N O P Q R S T U V W X Y Z
Min
3 5 8 2 1 0 6 3 2 7 5 1 2 4
(b) List the nodes that will be ignored by alpha-beta pruning, if child nodes are
visited left to right. Justify your answer showing the α-β values. (4 marks)
(c) In which order should moves {B,C,D,E} be examined (instead of left-to-
right) to maximize pruning? List the nodes pruned in this case. (2 marks)
(d) Indicate whether using a heuristics is required, optional, or unwanted in each
of the following cases, and state why. (3 marks)
solving the 8-puzzle:
playing tic-tac-toe:
playing chess:
END OF PAPER
6/6