FIT5047 Intelligent Systems

Practice Questions for Final Exam

1. [Agents] Consider the vacuum agent presented in class, but assume that the room

has 8 squares and a square can get dirty after it has been cleaned.

(a) Use PEAS to specify the task environment.

(b) Specify the attributes of the environment.

2. [Agents] Consider shopping for used AI books on the Internet.

(a) Use PEAS to specify the task environment

(b) Specify the attributes of the environment.

3. [Backtrack] Specify a state representation, operators and goal test to solve the N-

queen problem with N=4:

Four queens have to be placed on a 4X4 board where no row will have more than one

queen, no column will have more than one queen, and no diagonal will have more than

one queen.

Illustrate the workings of the backtracking algorithm (Backtrack1) to solve this prob-

lem.

4. [GraphSearch] Suppose we want to use the algorithm A* on the graph below to find

the shortest path from node S to node G. Each node is labeled by a capital letter and

the value of a heuristic function. Each edge is labeled by the cost to traverse that edge.

For this problem:

Perform the algorithm A* on this graph, filling in the table below. Indicate the

f , g, and h values of each node on the queue as shown in the first two rows of the

table. You need not write the contents of the (priority) queuen in order in the

table.

Assume that if you find a path to a node already on the queue that you update

its cost (using the lower f value) instead of adding another copy of that node to

the queue.

• Show the path found by the algorithm A* on the graph above.

iteration node expanded Priority queue at end of this iteration

•

2

0 S=0+6=6

1 S A=2+4=6; B=3+4=7

5. [Algorithm A*] The evaluation function f(n) = d(n) + W(n), where d(n) is the cost

of arriving at node n and W(n) is the sum of Manhattan Distance for each tile, is used

in conjunction with the algorithm A* to search from the start node:

2 8 3

1 6 4

7 5

To the goal node:

1 2 3

8 4

7 6 5

Use this evaluation function to search forward (from start node to goal node) and

backward (from the goal node to the start node). Where would the backward search

meet the forward search?

6. [Search] Which of the following are true and which are false? Explain your answers.

(a) Depth-first search always expands at least as many nodes as A* search with an

admissible heuristic.

(b) h(n) = 0 is an admissible heuristic for the 8-puzzle.

4

∃

7. [Game playing] Consider a game tree with branching factor 2 and depth 5. Assume

that it is MAX’s turn to play, and that the evaluation function at the leaf nodes is in

increasing order from left to right, such that its value for the leftmost node is 1, and

for the rightmost node is 16 (the leaf nodes are MAX nodes).

Conduct an α-β search of this game tree, starting from leftmost-node-first. In your

α-β tree, clearly indicate the propagation of the α and β values, the performed cutoffs

and the inspected leaf nodes.

Upon completion of the search, state the final backed-up value of the root node and

the recommended move (Left or Right). Also state the number of α and β cutoffs

performed, and the number of leaf nodes generated.

8. [First order logic] Assuming predicates PARENT (p, q) and FEMALE(p) and con-

stants Joan and Kevin, with the obvious meanings, express each of the following

sentences in first-order logic. (You may use the abbreviation 1 to mean “there exists

exactly one.”)

(a) Joan has a daughter (possibly more than one, and possibly sons as well).

(b) Joan has exactly one daughter (but may have sons as well).

(c) Joan has exactly one child, a daughter

(d) Joan and Kevin have exactly one child together.

(e) Joan has at least one child with Kevin, and no children with anyone else.

9. [First order logic] Consider a vocabulary with the following symbols:

OCCUPATION (p, o): Predicate. Person p has occupation o.

CUSTOMER(p1, p2): Predicate. Person p1 is a customer of person p2.

BOSS(p1, p2): Predicate. Person p1 is a boss of person p2.

Doctor, Surgeon, Lawyer, Actor: Constants denoting occupation.

Emily, Joe: Constants denoting people.

Use these symbols to write the following assertions in first-order logic:

(a) Emily is either a surgeon or a lawyer.

(b) Joe is an actor, but he also holds another job.

(c) All surgeons are doctors.

(d) Joe does not have a lawyer (i.e., is not a customer of any lawyer).

5

(e) Emily has a boss who is a lawyer.

(f) There exists a lawyer all of whose customers are doctors.

(g) Every surgeon has a lawyer.

10. [First-order logic] Indicate which of the following Predicate Calculus sentences are

correct representations of the corresponding English sentences, and explain why or why

not.

1 [∀x PERSON(x)] ⇒ [∃y MOTHER(y,x)]

Everybody has a mother

2 OLD(DOG(Fido))

Fido is an old dog

3 DOG(Fido) ∧ OLD(Fido)

Fido is an old dog

4 ∀x [ MATHEMATICAL-THEORY(x) ⇒ x ]

All mathematical theories are true

5 ∃s [ARISTOTLE-SAID(s) ∧ ¬TRUE(s)]

Aristotle told a lie

6 ¬∃v ∃b [BUTCHER(b) ∧ VEGETARIAN(v)]

There are no vegetarian butchers

7 ¬∃b ∃d BUTCHER(b) ∧ DOG(d) ∧ OWNS(b,d)

No butcher owns a dog

11. [First-order logic] The expression LAST(x,y) means that y is the last element of the

list x. We have the following axioms:

(a) LAST({u,NIL},u), where u is an element.

(b) LAST(y,z) ⇒ LAST({x,y},z), where x and z are elements, and y is a list.

Use the answer extraction method to find v, the last element of the list (2,1):

LAST({2,1,NIL},v)

12. [Unification] For each of the following pairs of literals indicate whether or not they

unify. If they do unify, show a most general unifier. If they do not unify, explain why

not.

(a) STRONGER(x, LexLuthor), STRONGER(LoisLane,y)

(b) HOLDING(x, Girlfriend(x)), HOLDING(Superman,y)

(c) FLY(Girlfriend(x)), ¬FLY(LoisLane)

(d) ¬LIKES(x,Enemy(x)), ¬LIKES(Enemy(y), y)

6

13. [Unification] For each pair of atomic sentences, give the most general unifier if it

exists. If they do not unify, explain why not.

(a) P (A, B, B), P (x, y, z).

(b) Q(y, G(A, B)), Q(G(x, x), y).

(c) OLDER(FATHER(y), y), OLDER(FATHER(x), John).

(d) KNOWS(FATHER(y), y), KNOWS(x, x).

14. [Resolution] From “Horses are animals”, it follows that “The head of a horse is the

head of an animal.” Demonstrate that this inference is valid by carrying out the fol-

lowing steps:

(a) Translate the premise and the conclusion into a well formed formula (wff) in First

order logic. Use three predicates: HEADOF (h, x) (meaning “h is the head of

x”), HORSE(x), and ANIMAL(x).

(b) Negate the conclusion, and convert the premise and the negated conclusion into

CNF.

(c) Use resolution to show that the conclusion follows from the premise.

15. [D-separation] According to this Figure, determine whether the following claims to

be True or False and justify your answer.

(a) B ⊥ G|A

(b) C ⊥ D|F

(c) C ⊥ D|A

(d) H ⊥ B|C, F

7

16. [Supervised Machine Learning] Consider the following dataset consisting of 3 bi-

nary features and a binary class variable.

Feature 1 Feature 2 Feature 3 Class

1 0 0 0

1 0 1 1

1 1 1 1

1 1 1 1

0 1 1 0

0 0 1 0

(a) Based on the dataset above, estimate the prior probability of Class 1.

(b) What is the initial entropy of the class labels over all the data? Show the formula

before plugging-in numbers.

(c) If we were to split the data into 2 groups based on the value of Feature 1, what

would be the entropy for each group?

(d) What is the Information Gain of Feature 1?

(e) You are told the Information Gain for Feature 2 and Feature 3 after splitting on

Feature1 is 0.08 and 0.19 respectively. Draw a decision tree for this problem.

(f) We will now build a Na¨ ıve Bayes model for predicting the class from these data.

Draw the Bayesian Network that corresponds to the Naive Bayes model.

(g) From the data table, write down the conditional probability estimates required for

the Na¨ ıve Bayes model.

(h) What class does the Na¨ ıve Bayes model predict for a new data item with values (1,

1, 1) for Features 1, 2 and 3 respectively? What is the probability of each class?

How does the Na¨ ıve Bayes classification compare to the decision tree classification?

17. [Decision Tree] Assume that you are given the set of labeled training examples

below, where each of three features has three possible values: a, b, or c. You choose

to learn a decision tree from these data.

F1 F2 F3 Output

ex1 c b b +

ex2 a a c +

ex3 b c c +

ex4 b c a -

ex5 a b c -

ex1 c a b -

What score would the information gain calculation assign to feature F1, when decid-

ing which feature to use as the root node for a decision tree being built? Be sure to

show all your work.

18. [K-nearest-neighbour] Assume we have the age, loan amount and pay result of some

customer from the bank. We need to predict the pay result of a new loan applicant

given only age and loan amount. The data are shown below:

Age Loan Amount (K) Pay Status

20 20 Paid

25 45 Paid

22 95 Default

35 53 Paid

35 120 Paid

33 150 Default

40 54 Default

45 75 Paid

52 20 Paid

49 220 Default

60 100 Default

A new bank customer with age 42 comes in and applies for a loan AUD$140K, how

would the 3-nearest-neighbour algorithm predict this customer? Paid or Default? Be

sure to show all your work.