CENG 405: ARTIFICIAL INTELLIGENCE

QUESTION ONE
(a) In each of the following question, please specify if the statement is true or false. If the
statement is true, explain why it is true. If it is false, explain what the correct answer
is and why.
(i) A search will always expand fewer search nodes than uniform cost search.
(ii) K-means is a clustering algorithm that is guaranteed to converge.
(iii) Sampling from a Bayes net using likelihood weighting will systematically
overestimate the posterior of a variable conditioned on one of its descendants.
(iv) For a two-player zero-sum game tree of depth 4 or greater, alpha-beta pruning
must prune at least one node.
(v) Inverse reinforcement learning (which makes helicopters fly by themselves) is
primarily concerned with learning an expert’s transition model.

(b) The table below shows the distance matrix for 5 objects.

A B C D E
A 0
B 9 0
C 3 7 0
D 6 5 9 0
E 11 10 2 8 0

(i) Design an algorithm to perform clustering of the objects into class using the
Single linkage Agglomerative Hierarchical Clustering method.
(ii) Use the algorithm in (i) to cluster the objects
(iii) Show the final result of the clustering in a dendogram tree using the single linkage
hierarchical clustering.

(c) The law says that it is a crime for an American to sell weapons to hostile nations. The
country Nono, an enemy of America, has some missiles, and all of its missiles were
sold to it by Colonel West, who is American.
(i) Prove that Col. West is a criminal [2
Marks]
(ii) Write an algorithm to perform forward chaining [2
Marks]
(iii) Use the forward chaining algorithm in a diagram to prove (i) [2
Marks]

Page 1|4 B. A. Weyori

 (d) A solved 8-puzzle game looks like this:

Given a puzzle state like the one above, where the numbers are in the wrong places, we want
to search for a series of moves that ends in the solution below. The number of moves required
could be calculated as a path cost.

(i) Write down a heuristic function, h, for this game (remember that this estimates the
path cost from a particular state to the solution). [2
Marks]
(ii) What is the value of h for the above board state? [1
Marks]
(iii) In a greedy search, what move would be chosen next? (i.e., move the 3, the 4
or the 6 into the gap?)
[2 Marks]
(iv)Is this heuristic admissible? [2
Marks]
(v) Can you suggest a better heuristic measure? [2
Marks]

(e) Three missionaries and cannibals are on one side of a river, along with a boat that can
hold one or two people. Find a way to get everyone to the other side, without ever
leaving a group of missionaries outnumbered by cannibals.
(i) Write the problem formulation for the task above? [1
Marks]
(ii) Solve the problem using the problem formulation? [2
Marks]

Page 2|4 B. A. Weyori

 (iii) Which of the following statements are true given the Bayesian network
below? For false statements, show one active trail.

(f)

(i) Design an algorithm to solve the graph above taking into consideration the cost
and the heuristic of each node
(ii) Apply the algorithm you designed in (i) to generate an optimized search path from
1 to 12.

(g) A company has an alarm for alerting the security of a disaster. The alarm is fairly
reliable at detecting a burglary and also responds at times to minor earthquakes. Two
of the workers on hearing the alarm ring call the disaster managing office. Jeremy,
one of the workers call the police when he hears the alarm ring, but sometimes
confuses the telephone ringing with the alarm and calls the police as well. Martha
who is the secretary of the company likes listening to very loud music and mostly
misses the alarm altogether. These are shown in the figure below.

(i) Compute the probability of the event that the alarm has sounded but neither a burglary
nor an earthquake has occurred and Jeremy calls but Martha misses the ringing sound
because she was listening to music and hence did not call?
(ii) Compute the probability of a Burglary given that Jeremy calls? [

Page 3|4 B. A. Weyori

 (h) Explain the difference between clustering and classification.
(i) When should you use classification over regression?
(j) What is Overfitting, and How Can You Avoid It?
(k) What is the difference between supervised and unsupervised machine learning?

Page 4|4 B. A. Weyori