CA318  Advanced Algorithms and AI Search  202324
Sample paper
Multiple choice
Answer all 20 multiplechoice questions. (2 marks each.) Total 40 marks.
No negative marking.
Only the filledin boxes will be looked at. No additional commentary or analysis will be read.
Remember to hand up the multiplechoice answer sheet!
 The input to the 7th output node of a neural network is:
x_{7} = w_{17} y_{1} + w_{27} y_{2} + w_{37} y_{3}
Then ∂x_{7} / ∂w_{27} is:
 y_{2}
 y_{j}
 w_{27}
 w_{jk}
 w_{jk}
 y_{j}
 A 3dimensional AND gate perceptron looks like:
 w_{1}=w_{2}=w_{3}=1, t=0
 w_{1}=w_{2}=w_{3}=1, t=3
 w_{1}=w_{2}=w_{3}=0, t=3
 w_{1}=w_{2}=w_{3}=1, t=1
 w_{1}=w_{2}=w_{3}=0, t=0
 w_{1}=w_{2}=w_{3}=0, t=1
 Why would we in practice not learn the function y = sin(x) + (1/x) from exemplars?
 We would learn it from exemplars.
 It would take too long.
 Learning it from exemplars is impossible for some values of x.
 Learning it from exemplars is impossible.
 It is a chaotic function.
 There is nothing to learn. The problem is solved.
 Divide by zero error.
 A problem has a branching factor of x. To examine all possible states between the current state and n steps into the future requires examining how many states?
 nx
 x+x^{n}
 x
 x + x^{2} + x^{3} + ... + x^{n}
 x^{n}
 n
 x^{x}
 n^{x}
 In machine evolution, we have 4 individuals, where individual i has fitness f(i):
i 1 2 3 4
f(i) 0 5 4 5
If we use a "Soft max" probability distribution with a "temperature" parameter T to choose who reproduces, then as T > infinity the probability of each individual reproducing goes to:

0 0.9 0.1 0.9

0 5/14 4/14 5/14

0 1 0 0

1/4 1/4 1/4 1/4

0 1/2 0 1/2

0 1 0 1
 In machine evolution, each individual has a genotype encoded in binary format. We repeatedly select 2 parents to make 2 children by copying the 2 genotypes, with the possibility of mutation and crossover. Let p_{c} be the probability of crossover between the 2 genotypes. Let p_{m} be the probability that any bit in the genotype mutates when it is inherited.
Each generation, we only pick the single best individual to be both parents of each child. Then:
 We rely on mutation to produce new solutions.
 Both mutation and crossover will produce new solutions.
 This is a normal search.
 No new solutions are produced.
 We rely on crossover to produce new solutions.
 Neural Networks and GAs can both be seen as hillclimbing on an unknown landscape by taking a finite number of samples. We consider E, the error in our solution, and the direction in which to change our solution. Which of the following is the case:
 For Neural Networks, E is known but is unknown. For GAs, neither E nor are known.
 For Neural Networks, E is known and is known. For GAs, E is known but is unknown.
 For Neural Networks, E is known and is known. For GAs, neither E nor are known.
 For Neural Networks, E is known and is known. For GAs, E is known and is known.
 In machine evolution, let the probability of an individual reproducing be its fitness divided by the sum of fitnesses of all individuals. Then:
 Fitness must be < 0
 Fitness can have any value.
 Fitness can have any value except zero.
 Fitness must be > 0
 Fitness must be ≤ 0
 Fitness must be ≥ 0
 In machine evolution, each individual has a genotype encoded in binary format. We repeatedly select 2 parents to make 2 children by copying the 2 genotypes, with the possibility of mutation and crossover. Let p_{c} be the probability of crossover between the 2 genotypes. Let p_{m} be the probability that any bit in the genotype mutates when it is inherited.
Only one of the following carries out a serious search of the state space. All the others are constrained by whatever happens to be the initial population. i.e. Only one of the following can generate all possible genotypes, given enough time:
 p_{m}=0, p_{c}=1
 p_{m}=0, p_{c}=0
 p_{m}=0.1, p_{c}=0
 p_{m}=1, p_{c}=0
 p_{m}=1, p_{c}=1
 We have a neural network where inputs are finite (positive or negative). If a node has a (positive) infinite threshold, then:
 If weights are positive, you have constant output 0.
 If weights are negative, you have constant output 1.
 If weights are finite, you have constant output 1.
 If weights are finite, you have constant output 0.
 If weights are negative, you have constant output 0.
 None of the above.
 If weights are positive, you have constant output 1.
 One of these is not a property of neural networks:
 Input is compared to previous Input, and "nearby" Input should produce "nearby" Output.
 It can be used to represent a function from realvalued singledimensional input to realvalued singledimensional output.
 As learning progresses, the size of the network remains fixed.
 It can be used to represent any normal linear, continuous, nonchaotic function.
 It can be used to represent a function from realvalued multidimensional input to realvalued multidimensional output.
 It can be used to represent a function from integervalued multidimensional input to integervalued multidimensional output.
 It can be used to represent any normal nonlinear, continuous, nonchaotic function.
 Given a network architecture, an Input leads to an Output after a fixed number of calculations.
 In neural networks, where w_{ij} is the weight connecting input node i with hidden node j, then input I_{i} is irrelevant to the workings of the network if:
 w_{ij} = 0 for all j.
 w_{ij} = 0 for no j.
 It is never irrelevant.
 w_{ij} = 0 for at least one j.
 It is always irrelevant.
 In a multilayer neural network, we have n hidden units with binary outputs, 1 output unit, weights w_{1},..,w_{n} connecting them, and threshold t for the output unit. Which one of the following implements an output unit that fires if and only if all the hidden units fire.
 w_{1}=w_{2}=..=w_{n}=0, t=1
 w_{1}=w_{2}=..=w_{n}=1, t=0
 w_{1}=w_{2}=..=w_{n}=W, W > 0, t=W
 w_{1}=w_{2}=..=w_{n}=W, W > 0, t=W+n
 w_{1}=w_{2}=..=w_{n}=W, W > 0, t=nW
 w_{1}=w_{2}=..=w_{n}=W, W > 0, t=n
 Consider a heuristic for human mate choice:
Have a relationship with n partners of fitness > f
Marry the next partner you find of fitness > g
where fitness is ranked by the individual out of 10.
Which of the following values for n,f,g (respectively) makes the most sense?
 0, 8, 3
 10, 5, 8
 10, 8, 3
 10, 0, 8
 0, 0, 8
 0, 5, 8
 Which is the correct ordering of these search methods, from the least work for the human programmer to the most work for the human programmer?
 Random search, Metaheuristic, Domainspecific heuristic
 Metaheuristic, Random search, Domainspecific heuristic
 Domainspecific heuristic, Metaheuristic, Random search
 Domainspecific heuristic, Random search, Metaheuristic
 Metaheuristic, Domainspecific heuristic, Random search
 Random search, Domainspecific heuristic, Metaheuristic
 Consider a heuristic for human mate choice:
Have a relationship with n partners of fitness > f
Marry the next partner you find of fitness > g
where fitness is ranked by the individual out of 10.
Which of the following values for n,f,g (respectively) makes the most sense?
 100, 8, 3
 10, 0, 8
 100, 5, 8
 100, 0, 8
 10, 8, 3
 10, 5, 8
 An upper bound on the statespace complexity of Xs and Os is:
 3^{3}
 9!
 9^{3}
 3^{9}
 3!
 9^{9}
 In machine evolution with asexual reproduction, mutation might break the parent's genotype and make it unfit. So therefore:
 We should set an appropriate mutation rate for the problem.
 We should only mutate at points that will improve the parent.
 We should only mutate about 1 in a million bits.
 We should mutate the unfit, not the fit.
 The original statement is not true.
 We should not mutate.
 We should mutate the fit, not the unfit.
 It is not something to worry about.
 In a perceptron, let inputs be 0 or 1. Let the output be y = 0 or 1, and the correct output be C. The Perceptron Learning Rule can be summarised as:
 If y=0 and C=1, then reduce threshold and increase weights.
 If y=0 and C=1, then increase threshold and reduce weights.
 If y=1 and C=0, then increase threshold and increase weights.
 If y=0 and C=1, then reduce threshold and reduce weights.
 If y=1 and C=0, then reduce threshold and increase weights.
 Define a perceptron that receives x and y as input and fires for these points:
a x  b y ≤ c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
 weights: a, b, threshold: c
Long questions
Answer 2 long questions out of 4. (25 marks each.) Total 50 marks.
 Each question gives maximum number of sentences for the answer. Do not exceed this.
 You might like to write your answers as rough work first to figure out what sentences to use.
Make sure any rough work is crossed out.
 Put your sentences as bullet points not a paragraph.
 If you answer more than 2 questions, I will pick the best 2.
Question 1  [Total marks: 25] 
1(a) 
Is this function y = f(x) easy or hard to maximise from exemplars?
f(1.0372) = 80.
f(1.0373) = 100.
f(x) = 0 for all other x.
Maximum length: 3 sentences 
[5 marks] 
1(b) 
Consider trying to maximise a function
of x, where x is an integer from 1 to 10^{20}.
There are seven (and only seven) values of x where f(x) = 10.
For all other x, f(x) = 1.
The machine is not told this but has to find out by trial and error.
What would maximising this function by trial and error look like?
Maximum length: 3 sentences 
[5 marks] 
1(c) 
Mathematicians have longstanding tools to maximise functions
and calculate function values.
What is different about the "functions" AI programs try to maximise
and calculate values for?
Maximum length: 3 sentences 
[5 marks] 
1(d) 
We believe that some function exists from
ndimensional input x to output f(x).
That is, we can set up our system with input x and some process will give us a value for f(x).
We have no equation for f.
Contrast representing f(x)
with maximising f(x).
Maximum length: 3 sentences 
[5 marks] 
1(e) 
Discuss trying to maximise the following function from exemplars.
Explain what would happen during learning.
Input x is a number. It does not include the clock time.
The function is defined as follows:
if ( x > 10 )
f(x) = 1 if clock time is PM.
f(x) = 1 if clock time is AM.
else if ( x < 10 )
f(x) = 1 if clock time is PM.
f(x) = 1 if clock time is AM.
else f(x) = 0
Maximum length: 3 sentences 
[5 marks] 
Question 2  [Total marks: 25] 
2(a) 
When a problem is represented as a State Space Search problem,
the "search tree" is drawn. True or false?
Maximum length: 1 sentence 
[5 marks] 
2(b) 
Imagine the following situation in Bestfirst search.
The heuristic evaluation function tells us a state is 4 steps away from the goal.
We examine the children of this state and the heuristic evaluation function
tells us all of them are 5 steps away from the goal.
Can this happen?
Maximum length: 2 sentences 
[5 marks] 
2(c) 
In Bestfirst search what would happen if you add a constant c
to every result returned by the heuristic evaluation function?
Maximum length: 2 sentences 
[5 marks] 
2(d) 
In the Travelling Salesman Problem with n cities,
we say there is an upper bound of (n1)! on the number of paths to be searched.
What assumption did we just make?
Maximum length: 2 sentences 
[5 marks] 
2(e) 
In the Npuzzle problem, we use a heuristic (distance to goal estimate) as follows:
h(n) = number of pieces out of place.
If h(x) = 5 and h(y) = 3 then is y a better state than x?
Maximum length: 2 sentences 
[5 marks] 
Question 3  [Total marks: 25] 
3(a) 
A mobile robot has
Input state = (angle of direction of nearest wall, velocity value).
Output behaviour = one of (turn left, turn right, stop, keep going).
The Input state is clearly missing some information.
What are the consequences of this missing information?
Maximum length: 3 sentences 
[5 marks] 
3(b) 
We are trying to build a character recognition program.
Characters are images of 100 x 100 pixels.
We are trying to recognise the digits "0" to "9".
Output is 1 dimensional so therefore the output vector should be 1 dimensional. True or false?
Maximum length: 3 sentences 
[5 marks] 
3(c) 
In a neural network, the network generates a (vector) output
y = (y_{1},..,y_{n}).
We then tell it the "correct" output
O = (O_{1},..,O_{n}).
Consider the following as a measure of "error" E:
Why is this a bad measure of the error?
Maximum length: 3 sentences 
[5 marks] 
3(d) 
In supervised learning with a neural network,
we show the network an Input, and then show it the correct Output.
The network modifies its weights so that next time
it sees the input, it will be more likely
to generate the correct output.
Why such a roundabout method?
Why not simply remember the correct output
and return it exactly next time it is asked?
Maximum length: 2 sentences 
[5 marks] 
3(e) 
Given a line in 2dimensional space:
a x + b y = c
Define a perceptron that
fires if and only if the point is on this side of the line:
a x + b y <= c
Maximum length: 3 sentences 
[5 marks] 
Question 4  [Total marks: 25] 
4(a) 
In a genetic algorithm (GA),
let p_{c} be the probability of crossover.
What would happen if p_{c} = 1?
Maximum length: 2 sentences 
[5 marks] 
4(b) 
In a genetic algorithm (GA),
let each individual i have fitness f(i),
and let its probability of reproducing, p(i), be:
where T is the "temperature".
Show that if all fitnesses are the same, we pick a random individual.
Maximum length: 2 sentences 
[5 marks] 
4(c) 
Consider crossing over two parents to produce two offspring.
The parents are binary bitstrings.
Name two circumstances under which the crossover operation will
not produce any new diversity.
Maximum length: 2 sentences 
[5 marks] 
4(d) 
In a genetic algorithm (GA),
let p_{m} be the probability that any bit in the
chromosome mutates
at the point where it is inherited from the parent by the child.
Let the chromosome be binary, so that mutation means a bit flip.
What would happen if p_{m} = 0 (but you still had crossover)?
Maximum length: 4 sentences 
[5 marks] 
4(e) 
In a genetic algorithm:
What would happen if you had a variable (rather than a constant)
population size?
Maximum length: 3 sentences 
[5 marks] 
Bonus question
Bonus question. (10 marks.)
It is "bonus" because I tell you it in advance.
The question is to make you do some reading. You can prepare this question in advance.
Bonus question:
Tell me about some AIrelated algorithm or software
that was not mentioned on the course.
CA318  Advanced Algorithms and AI Search
Answer sheet
Black out the square that matches the correct answer.
Exam No:_____________________
Class:_____________________
Seat No:_____________________

Question 
1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
1         
2         
3         
4         
5         
6         
7         
8         
9         
10         
11         
12         
13         
14         
15         
16         
17         
18         
19         
20         

