Student Number: Last Nrune: First Name: Signature:
Introduction to Artificial Intelligence Duration – 4 hours
Do not turn this page until you have received the signal to start. (In the meantime, please fill out the identification section above, and read the instructions below carefully.)
This final examination consists of 7 questions on 18 pages
(including this one). When you receive the signal to start,
please make sure that your copy of the examination is complete.
Answer each question directly on the examination paper, in the
space provided, and use the reverse side of the pages for rough #3: 12 work. (If you need more space for one of your solutions, use the
reverse side of the page and indicate clearly which part of your work should be marked.)
Good Luck!
#4: #5:
#1: 12 #2: 12
20
20
#6: 14 #7: 10
TOTAL: 100
Total Pages= 18
Page 1
CONT’D…
Final Examination
Question 1. Search [12 MARKS]
Consider the problem of searching the following graph with A being the start state and G being the goal state. Each edge in the graph is labeled by its cost, and the heuristic value of each node n in the graph, h(n), is also indicated. For example, h(A) = 18 and c(A ➔ D) = 4.
h(A) = 18 h(B) = 10 h(C) = 4 h(D) = 4 h(E) = 4 h(F) = 6 h(G) = 0
Trace the execution of A* on the graph. Assume that no cycle checking is
(a) {6 MARKS]
performed. Show the successive configurations of the frontier where the elements on the frontier
are paths. That is, the path n1 ➔ n2 ➔ ns would be written as {n1, n2, ns]. Next to each path of the frontier, indicate the f value of the final node in the path (e.g., if f(ns) = 10 write “10” next to the path and enclosed in parens with the path)’. Indicate the path that is expanded at each stage. Break ties (if there are any) by expanding the path most recently added to the frontier first.
Iteration
0
1
2
3
4
5
6
7
8
9
10
(b) [2 MARKS]
Node Expanded
Frontier ([A],18)
Total Pages = 18
Page 2
CONT’D …
The path to the goal found by A*is:
Final Examination
Trace the execution of uniform cost search on the graph. Assume that no
h(A) = 18 h(B) = 10 h(C) = 4 ·· h(D) = 4
h(F) = 6 h(G) = 0
(c) [4 MARKS]
cycle checking is being performed. Show the successive configurations of the frontier (as before the elements of the frontier are paths written in reverse order). Next to each path of the frontier, indicate the cost of the path. Indicate the path that is expanded at each stage. Expand nodes bottom to top. Break ties by expanding the path that was more recently added to the frontier first.
Iteration
0
1
2
3
4
5 6 7 8 9 10
[2 MARKS]
Node Expanded
Frontier ([A],O)
(d)
The path to the goal found by uniform cost is:
Total Pages = 18
Page 3
CONT’D …
h(E) = 4
Question 2. CSP (12 MARKS]
Final Examination
Consider the following layout for a crossword puzzle.
12 3
4
If you do not know what a crossword puzzle is read this paragraph. A crossword puzzle consists of a grid of white and black squares. The numbered squar�s are white squares that start a sequence of white squares going across from left to right, or going down from top to bottom. For example, the white square 1 starts a sequence of three white squares going across and a sequence of four squares going down. A crossword puzzle is solved by placing letters into the white squares so that every numbered across sequence and every numbered down sequence forms a word. For example the sequence of letters ‘T’, ‘H’, ‘E’, ‘N’, might be put top to bottom in the white squares starting at square number 1 as these four letters form a word. Normally, however, the words that can be put into the grid must also satisfy other conditions.
We want to solve this puzzle so that its solution includes only words from the following set {big, bus, car, has, oar, balm, book, buys, hold, lamb, beast, ginger, search, symbol, syntax}.
That is, we want to fill in the crossword using only words from this set (of course not all words can be used). To do this we set up the crossword as a CSP problem. The variables we use are 1a, 1d, 3a, 2d, 4a, where “a” means across and “d” means down. Each variable’s domain is a word from our set of words that can fit into the corresponding sequence of boxes. For example, assigning a word to the variable 1a corresponds to placing a three letter word into the 3 boxes starting box number 1 and going across (left to right). Similarly assigning a word to the variable 1d corresponds to placing a four letter word into the 4 boxes starting at box number 1 and going down.
Total Pages= 18
Page 4
Final Examination
Answer the following questions:
(a) [2 MARKS] Using the crossword description, specify the domain of each variable.
Variable Domain
la 1d 2d 3a 4a
(b) [6 MARKS]
C4(2d, 3a), and Cs(2d, 4a), one between each pair of variables that “shares a letter”. For each constraint give the set of satisfying tuples in the first table on the next page, where the values in the tuples are ordered according to the constraint’s scope. For example, for 01(la, ld) the satisfying tuples will contain two values, a value for variable la followed by a value for variable ld.
(c) [4 MARKS] Give the final GAC consistent Variable domains in the second table on the next page.
There are five constraints in the CSP model C1(la, ld), C2(la, 2d), C3(ld, 3a),
Total Pages= 18
Page 5
CONT’D …
Give answer to question (b) in this table. Constraint
C1(la, ld)
C2(la, 2d)
Ca(ld, 3a)
C4(2d, 3a)
C5(2d, 4a)
Give answer to question (c) in this table. Variable
la
1d 2d 3a 4a
Satisfying Tuples
Final Examination
Final OAC Domain
Total Pages= 18
Page 6
CONT’D …
Final Examination
Question 3. Logi� [12 MARKS] (a) (6 MARKS]
1. What are the two types of atomic well-formed formulas in first-order logic?
2. (a) Translate the following English sentence into first-order logic, using only these predicates:
Ernployed(x), HasJobAt(x, y), Company(x), SelfEmployed(x):
A-person is employed, if that person has a job at some company or that person is
self-employed.
(b) Give an interpretation that falsifies the sentence you gave in your answer to part (a) of this question.
Total Pages = 18 Page 7
CONT’D …
Most General Unifier:
Final Examination
(b) [6 MARKS] ·For each of the pairs below, give the most general unifier (MGU) or state why no unifier exists. If a unifier exists, provide the expression that results from the unification. In all
of the expressions that follow, the only variables are x, y, and z. 1. P(g(x),f(a),y) and P(y,f(x),g(z))
2. P(g(x),y,J(x,y)) and P(z,h(x),J(c,h(x)))
3. f(g(x,x),h(b,x)) and f(y,h(b,f(y,y)))
Total Pages= 18 Page 8
CONT’D …
Final Examination
Question 4. Resolution [20 MARKS]
(a) [5 MARKS] Given predicates P, Q, Rand constants a, b, c; convert the following sentences to clausal form:
1. ‘v’x[R(x) :J P(a, x)]
2. Q(a,c)VQ(b,c)
3. \ix[3z(R(z)I\Q(x,z)):)\iw.,P(w,x)]
4. R(c)
5. \ix[\iy(R(y) 🙂 P(x, y)) :J 3z.P(z, x)]
Total Pages= 18
Page 9
CONT’D…
Final Examination
(b)[15 MARKS] Use the clauses you generated in part (a) to show using Resolution that
{1, 2, 3, 4, 5} F Q(b, c).
Total Pages = 18 Page 10
Final Examination
Question 5. Planning [20 MARKS)
In this question we shall consider the formalization of a Turing Machine in STRIPS. Recall that a Turing Machine has an infinite tape composed of squares and a head above the tape that can move one square to the left or right, and write a character to the square where it is located. In this representation, there is no ‘read’ action, but rather the contents of the tape are accessible to the head via the Tape predicate. You may assume the following predicates:
1. Tape(k, c): the tape square numbered k contains character c, 2. Location(k): the head is located at square k, and
3. Character(c): c is a legal character.
The possible actions are:
1. left: move the head one square to the left,
2. right: move the head one square to the right, and
3. write(c), where c is a legal character, writes c at the current location of the head.
Moreover, so as to simplify matters, consider the case where the tape extends infinitely in one direction only, with squares numbered from O and continuing infinitely to the right. The head cannot go past the left-hand end of the tape.
You may use the addition (+) and subtraction (-) functions, the integer relational operators (=, =/=, <, $, >, �) and assume there are constant symbols for the non-negative integers 0( , 1, 2, …). Formalize the three actions above in STRIPS, using the above predicates to specify sensible pre conditions and effects for each of the actions.
Total Pages= 18 Page 11
CONT’D …
Final Examination
TIDS IS AN EXTRA PAGE FOR Q5
Total Pages= 18
Page 12
CONT’D …
Final Examination Question 6. Bayes Net (14 MARKS]
In the Bayesian Network above, which models the probability of a candidate being elected, F= Female, .H = Honest, P= Popular, T = Tied to Special Interest Groups , E = Elected and all variables are Boolean. In the tables below we use upper case to indicate the variable and lower case to indicate the values of a variable.
The conditional probability tables for the network are:
��TtEep p �� h 3/10 p 3/5 f/\h/\t 9/10
-h 9/10 -p 9/10 f/\h/\-t 2/5 f /\ -h /\ t ·4/5 f /\ -h /\ -t 1/5 -f /\ h /\ t 4/5
-f /\ .h /\ -t 3/10
Total Pages= 18
Page 13
CONT’D …
-f /\ -h /\ t -f/\-h/\-t 1/10
4/5
Final Examination
(a) [2 MARKS] Which of the following statements are asserted by the network above? 1. P(F,T)=P(F)P(T)
2. P(EIP,T)=P(EIP,T,H)
3. P(PIF,H)=P(PIF,H,T)
(b) [1 MARK] If we use variable elimination on this network to eliminate H, T, and P, what would be a better elimination order: (a) H, T, P, or (b) P, T, H? (Answer a or b)
· (c) [3 MARKS] Using d-separation, list the pairs of individual nodes that are conditionally independent in this network
1. (1 mark) When there is no evidence.
2. (1 mark) When the candidate is Popular.
3. (1 marks) When the candidate has Ties to Special Interest.
(d) (2 MARKS] Calculate P(f, h, -t,p, -e)
Total Pages= 18
Page 14
CONT’D …
(e)
[4 MARKS] Calculate P(Flh, -t, e)
Final Examination
(f) [2 MARKS] If two candidates run for office, can we copy this network and expect the two networks, together, to accurately represent the joint distribution over the variables related to the two candidates? Why or why no�?
Total Pages = 18 Page 15
CONT’D …
Final Examination
Question 7. Probability [10 MARKS]
The Surprise Candy Company makes candy in two flavours: 70% are strawberry and 30% are anchovy. The flavours are randomly deposited into either square or round molds. After hardening in the mold, each candy piece is wrapped in a randomly chosen red or brown wrapper. 80% of the strawberry candies are round and 80% have a red wrapper, while 90% of the anchovy candies are square and 90% have a brown wrapper. All candies are sold as individual pieces that are packed and sealed in identical black boxes.
You, the customer, just bought a Surprise Candy at the store but have not yet opened the box. Consider the following three Bayes Networks.
(A)
(B)
(C)
Total Pages = 18
Page 16
CONT’D …
(a)
(b)
(c)
[2 MARKS]
(2 MARKS]
[2 MARKS]
Final Examination
Which network(s) can correctly represent P(Flavour, Wrapper, Shape)? Which network is the best representation of the problem?
What’s P(Wrapper = red)?
(d)
[4 MARKS]
What’s P(Flavour = strawberry!Wrapper = red, Shape= round)?
Total Pages = 18
Page 17
CONT’D …
Final Examination
THIS IS AN EXTRA PAGE FOR ROUGH WORK.
Total Pages= 18
Total Marks = 100 Page 18 -.
END OF EXAMINATION