National University of Computer and Emerging Sciences

Department of Computer Science

CS 401 – Artificial Intelligence

Mid-Term I (SPRING 2017)-[Solution]

Instructors: Zain Iqbal

February 22, 2017

Total Marks:52 Time Allowed: 60 minutes

Instructions:

(1) Understanding the question is part of exam. NO QUERIES WILL BE ENTERTAINED.

(2) Provide answers in the given space.
(3) Write in legible hand writing.
(4) Use permanent ink pens only.
(5) Multiple answers will not be marked. In case of ambiguity, ZERO points will be
assigned to the respective question(s).

Roll No. _________________ Section: _________

Question 1 2 3 4 5 Total

Marks 07 13 10 12 10 52

Obtained

GOOD LUCK 
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

Question 1: Marks 3+1x4=07

Consider the search graph given below with S as the start state and G as the goal state.

a. Draw the complete search tree for this graph. Label each node in the tree with the cost of the path to that node and
the heuristic cost at that node. Be very careful as your answers to the following questions will be incorrect if you made
a mistake in the tree.

Solution:

Page 2 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

b. For each of the searches below, just give a list of node names (state name, length of path) drawn from the tree above.
Break ties using alphabetical order. Refer to the states with their names and the cost of the path to that node. Trace
algorithms very carefully, no partial credit will be given for any of these.

NOTE: we used the following two terms: visited list and expanded list which refers to open and closed list respectively.

i. Perform a depth-first search using a visited list. Assume children of a state are ordered in alphabetical order.
Show the sequence of nodes that are expanded by the search.
S0, A3, C5, G5

ii. Perform a best-first (greedy search) without a visited or expanded list. Show the sequence of nodes that are
expanded by the search.
S0 (h=5), A3(h=2), G5(h=0)

iii. Perform a Uniform Cost Search without a visited or expanded list. Show the sequence of nodes that are
expanded by the search.
S0, B1, C2, A3, A4, C5, G5

iv. Perform an A* search without an expanded list. Show the sequence of nodes that are expanded by the search.
S0(0+5), B1(1+3), C2(2+2), A3(3+2), G5(5+0)

Page 3 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

Question 2: Marks 4+2+4+1+2= 13

CSPs

You are in charge of scheduling for computer science classes that meet Mondays, Wednesdays and Fridays. There are 6
classes that meet on these days and 3 professors who will be teaching these classes. You are constrained by the fact that
each professor can only teach one class at a time.
The classes are:
 Class 1 - Intro to Programming: meets from 8:00-9:00am
 Class 2 - Intro to Artificial Intelligence: meets from 8:30-9:30am
 Class 3 - Natural Language Processing: meets from 9:00-10:00am
 Class 4 - Computer Vision: meets from 9:00-10:00am
 Class 5 - Machine Learning: meets from 10:30-11:30am
The professors are:
 Professor A, who is available to teach Classes 1, 2, and 5.
 Professor B, who is available to teach Classes 3, 4, and 5.
 Professor C, who is available to teach Classes 1, 3, and 4.

a) Formulate this problem as a CSP problem in which there is one variable per class, stating the domains, and
constraints. Constraints should be specified formally and precisely, but may be implicit rather than explicit.

Page 4 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

b) Draw the constraint graph associated with your CSP.

c) Show the domains of the variables after running arc-consistency on this initial graph (after having already
enforced any unary constraints).

Page 5 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

d) Give one solution to this CSP

C1=C, C2=A , C3=B/C C4=C/B C5=B/A

e) Your CSP should look nearly tree-structured. Briefly explain (one sentence or less) why we might prefer to solve
tree-structures CSPs.

Question 3: Marks 2+2+4+2 = 10

a. Suppose you have a CSP problem, and you run arc consistency starting from the initial state (before any variables are
assigned). After applying arc consistency, all variables have one or more possible value, and there is a variable Vi
whose domain Di has exactly one possible value remaining (|Di| = 1). Based on this assumption, state whether each
of the following statements is TRUE or FALSE and provide valid reasoning to justify your answer to get any credit.

i. There must be at least one solution to this CSP problem.

Answer: False. Arc consistency does not remove all impossible assignments, so we do not know if the
remaining possible value corresponds to a solution or not.

ii. Any solution to this CSP problem must have the variable Vi instantiated to the value in Di.
True. Since arc consistency only eliminates impossible assignments, we know that any solution must use the
remaining assignments.

b. Give an example of an admissible but inconsistent heuristic i.e. you would need to provide a state-space graph and
then specify a heuristic function satisfying both conditions.

Page 6 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

C
10
10
S A G
10 20
10
B

S A B C G

Heuristic H1 25 20 15 10 0

Heuristic H2 25 20 3 10 0

H2 is a example of it

Question 4: Marks 4+3+3+2 = 12

Search: Mr. and Ms. Pacman
Mr.Pacman and Ms. Pacman are lost in an NxN maze and would like to meet; they don't care where. In each time step,
both simultaneously move in one of the following directions: fNORTH, SOUTH, EAST, WEST, STOPg. They do not
alternate turns. You must devise a plan, which positions them together, somewhere, in as few time steps as possible.
Passing each other does not count as meeting; they must occupy the same square at the same time.

a) Formally state this problem as a single-agent state-space search problem.

I. States:

II. Maximum size of state space:

III. Maximum branching factor:

Page 7 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

IV. Goal test:

b) Give a non-trivial admissible heuristic for this problem.

c) Circle all of the following graph search methods which are guaranteed to output optimal solutions to this
problem:
i. DFS
ii. BFS
iii. UCS
iv. A* (with a consistent and admissible heuristic)
v. A* (with heuristic that returns zero for each state)
vi. Greedy search (with a consistent and admissible heuristic)
d) If h1 and h2 are admissible, which of the following are also guaranteed to be admissible? Circle all that apply:

Question 5: Marks 10

Consider the following tree. Apply Recursive Best First Search algorithm to find the solution and clearly show every
iteration.

Page 8 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

Page 9 of 10
 National University
Of Computer & Emerging Sciences Faisalabad -Chiniot Campus

[The page is intentionally Left Blank for Solution]

Page 10 of 10