Question 1 – Search [30 marks]
a) Compare the following search strategies in terms of completeness and optimality:
i. Breadth-first search.
ii. Depth-first search.
iii. Depth-first search with iterative deepening.
iv. Greedy search.
[8 marks]
b) Explain in your own words what is meant by ‘a heuristic search strategy’ and ‘an
admissible heuristic’. Give an example of a search heuristic which is not discussed
elsewhere in this coursework.
[6 marks]
c) For this question you will need to use the simplified map of Romania and the table of
straight-line distances to Bucharest from Chapter 3 of AIMA.
Calculate the route that would be chosen from Zerind to Bucharest by each of:
i. Greedy search.
ii. A* search.
You should explain your answers and show your working. Detailed content such as
successive states of the search tree may be given in an appendix.
[16 marks]
3
Question 2 – Logic and reasoning [40 marks]
a) This question involves the notions of consistency and validity in the context of formal
logic. You should read through the Oxford tutorial on consistency and validity before
answering this question.
i. Show using truth tables whether the following set of sentences is consistent or
inconsistent. Begin by explaining in your own words what is meant by
consistency in the context of formal logic.
A ˄ (B v C)
(A ˄ B) v C
¬B
ii. Show using truth tables whether the following set of sentences is consistent or
inconsistent:
A ˄ (B → C)
(A v B) → C
¬C
iii. Is the argument below valid or invalid? Justify your answer. Begin by explaining
in your own words what is meant by validity in the context of logical reasoning.
‘If it rains the grass gets wet. It has not rained. Therefore the grass is not wet.’
iv. Is the argument below valid or invalid? Justify your answer.
‘If water is heated to 100°C it will boil. The water has not boiled. Therefore it
has not been heated to 100°C.’
[10 marks]
b) For this question you should use reasoning patterns which are either explicitly listed in
the subject guide, pp.20–22, or can be produced using the logical equivalences in Figure
4.1 of the guide. Explain whether the ‘proofs’ in i-iii below are correct according to the
reasoning patterns and equivalences given in the guide. If not, give a correct proof
showing what can be inferred from the knowledge base provided. Show all steps in your
reasoning and explain your answers.
i. Knowledge base:
- A ˄ B
- B → (C → D)
- A → ¬D
Proof:
A ˄ B/A
A ˄ B/B
B → (C → D),B/ C → D
A, A → ¬D/¬D
¬D, C → D/¬C
4
ii. Knowledge base: - ¬(A ˄ B)
- A v B
- B → C
- ¬C
Proof:
¬(A ˄ B)/¬A ˄ ¬B
¬A ˄ ¬B/¬A
A v B, ¬A/B
B → C, B/C
iii. Knowledge base: - ¬(A v B)
- A → C
- C ↔ D
- D → B
Proof:
¬(A v B)/¬A ˄ ¬B
¬A ˄ ¬B/¬A
¬A, A → C/¬C
¬C, C ↔ D/¬D
[10 marks]
c) This question involves Predicate Calculus. Suppose you are playing a board game that
involves using counters with from three to seven sides, which can be red, blue or green.
Your allocation of counters for the current game is shown below.
Triangle: 6 red, 4 green, 0 blue
Rectangle: 3 red, 0 green, 0 blue
Pentagon: 1 red, 1 green, 0 blue
Hexagon: 0 red, 0 green, 8 blue
Heptagon: 0 red, 0 green, 0 blue.
For each of the following formulas i-v, you should write out the literal meaning in English,
express it in ordinary language and explain whether it is true or false in this setting.
For example:
¬ⱻx(Rectangle(x) ˄ Red(x))
Literal meaning: There is no x, such that x is a rectangle and x is red.
Ordinary language: No rectangles are red or there are no red rectangles.
True or false? False: there are in fact three red rectangles.
5
i. Ɐx(Triangle(x) → (Red(x) v Green(x)))
ii. ¬ⱻx(Rectangle(x) → (Green(x))
iii. ⱻx(Pentagon(x) ˄ (Red(x) ˄ Green(x)))
iv. Ɐx(Hexagon(x) ˄ Blue(x))
v. Ɐx(Heptagon(x) → Blue(x))
Finally, express the following statements as formulas of Predicate Calculus and explain
whether they are true or false. You should explain the intended meanings of any constant
terms or predicates you use.
vi. All counters with an even number of sides are red or blue.
vii. No counters with an odd number of sides are blue.
[20 marks]
Question 3 – Probabilistic reasoning [30 marks]
a) This question concerns the probabilities of outcomes of a roll of two fair, standard sixfaced dice. We are concerned with three possible types of outcome:
doubles = the two dice have the same values.
total_gt6 = the sum of the numbers on the two dice is greater than 6.
total_lt9 = the sum of the numbers on the two dice is less than 9.
These can be treated as abbreviations for assignment of the values true or false to
the random variables Doubles, Total_gt6 and Total_lt9.
i. Draw a 6 x 6 grid showing all possible values of the two dice. Indicate which of
the above propositions is true for each cell in the grid.
ii. Draw a table showing the joint probability distribution of Doubles, Total_gt6,
and Total_lt9. Give your results both as fractions and in decimal, to three
significant figures.
iii. Using the values from your distribution, calculate the following probabilities by
marginalisation. Show all your working.
- P(doubles)
- P(total_gt6)
- P(total_lt9)
iv. Calculate the following conditional probabilities. Show all your working. - P(doubles|total_gt6)
- P(¬doubles|total_gt6)
- P(total_gt6|total_lt9)
v. Calculate the following using the product rule. Show all your working. - P(doubles ˄ total_gt6)
- P(total_gt6 ˄ total_lt9)
vi. Finally, show how Bayes’ Rule can be derived from the product rule and use it
to calculate P(total_gt6|doubles). Show all your working.
[20 marks]
6
b)
i. Explain in general terms what it means to say that two (or more) variables are
independent in the context of probability.
ii. Russell and Norvig give three forms of independence between propositions:
P(a|b) = P(a); P(b|a) = P(b); P(a ˄ b) = P(a)P(b).
Show that these three forms are equivalent.
iii. Based on the above definitions, are doubles and total_gt6 independent?
iv. Again, according to the above definitions, are total_gt6 and total_lt9
independent?
Justify your answers.
[10 marks]
[Total 100 marks]
[END OF COURSEWORK ASSIGNMENT 1]