CA318 - Advanced Algorithms and AI Search - Sample paper

Instructions:
Answer all 10 multiple-choice questions. (3 marks each.) Total 30 marks.
Answer 2 long questions out of 4. (30 marks each.) Total 60 marks.
Answer the bonus question. (10 marks.)
Remember to hand up the multiple-choice answer sheet!

Multiple choice

  1. In AI search, the following heuristic: 
    Initialise with 10 random solutions. 
Repeat forever
{
  Pick the best solution.
  Make 10 new solutions by making small or no changes to it.
}
    might be a bad heuristic because:
    1. 10 is too small.
    2. 10 is too large.
    3. It tends to lose good solutions once found.
    4. Small changes may break the best solution.
    5. It tends to converge on local optima.
    6. It tends to converge on global optima.
    7. It is not a bad heuristic.
    8. It is not a heuristic.

  2. Consider a heuristic for human mate choice: 
    Go out 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?
    1. 0, 0, 8
    2. 0, 5, 5
    3. 0, 5, 8
    4. 0, 8, 5
    5. 10, 0, 8
    6. 10, 5, 5
    7. 10, 5, 8
    8. 10, 8, 5

  3. Playing chess requires what heuristics?
    1. Heuristic search, and heuristic evaluation function.
    2. Heuristic search only.
    3. Heuristic evaluation function only.
    4. No heuristics.

  4. 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?
    1. Domain-specific heuristic, Metaheuristic, Random search
    2. Domain-specific heuristic, Random search, Metaheuristic
    3. Metaheuristic, Domain-specific heuristic, Random search
    4. Metaheuristic, Random search, Domain-specific heuristic
    5. Random search, Domain-specific heuristic, Metaheuristic
    6. Random search, Metaheuristic, Domain-specific heuristic

  5. The periodic nature of f(x) = sin(1/x) is expressed by the fact that:
    1. f ( x ) = f ( x+2π ) for any x
    2. f ( x ) = f ( x+2 ) for any x
    3. f ( x ) = f ( x+2n ) for any n
    4. f ( 1/x ) = f ( 1/(x+2π) ) for any x
    5. f ( 1/x ) = f ( 1/(x+2) ) for any x
    6. f ( 1/x ) = f ( 1/(x+2n) ) for any n

  6. We have two exemplars: 
    Temperature 22 degrees, pressure 1000 mb. Rain.
Temperature 15 degrees, pressure 990 mb. No rain.
    Then the question is: 
    Temperature 17 degrees, pressure 1010 mb. Will there be rain?
    We predict by Hamming distance to the nearest exemplar, (a) with pressure in millibars, (b) with pressure in bars. What does it predict?
    1. (a) Rain, (b) No rain
    2. (a) Rain, (b) Rain
    3. (a) No rain, (b) No rain
    4. (a) No rain, (b) Rain

  7. In machine evolution, our chromosome is a binary string of length n. We interpret it as encoding an integer x. To convert this to encoding a real number in the interval a to b, we calculate:
    1. x/(2n)
    2. x/(2n-1)
    3. a + x (b-a)
    4. a + x / (b-a)
    5. a + (x/(2n-1)) (b-a)
    6. x / (b-a)

  8. We have n individuals. Let each individual i have fitness f(i), and let its probability of reproducing, p(i), be:
    where T is the "temperature".
    All fitnesses are different.
    As   T -> infinity   the probability of picking the individual with the lowest fitness goes to:
    1. 1
    2. 0
    3. infinity
    4. n
    5. T
    6. 1/n
    7. 1/T

  9. 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: 

    1.  0    1     0     0 			
    2.  0    1/2   0     1/2 		
    3.  0    1     0     1 			
    4.  0    5/14  4/14  5/14 		
    5.  0    0.9   0.1   0.9 		
    6.  1/4  1/4   1/4   1/4

    respectively.

  10. In machine evolution, we have 4 individuals, where individual i has fitness f(i): 
    i     1   2   3   4
f(i)  0  -1  -2  -1
    If we use a "Soft max" probability distribution with a "temperature" parameter T to choose who reproduces, then as   T -> 0   the probability of each individual reproducing goes to: 

    1.  0    0     1     0 		
    2.  0    1     1     1 			
    3.  0    1/4   1/2   1/4 		
    4.  0    1/2   0     1/2 		
    5.  0    1     0     1 			
    6.  1    0     0     0 		
    7.  1/4  1/4   1/4   1/4

    respectively.

Long questions

1(a)   Explain the Hamming distance as a measure of difference between 2 vectors.

[6 marks]
1(b)   Given exemplars: 
Temperature 22 degrees. No rain.
Temperature 15 degrees. Rain.
Then the question is: 
Temperature 17 degrees. Will there be rain?
Explain your answer.

[6 marks]
1(c)   Say we gathered more weather data. Let the exemplars be: 
Temperature 22 degrees, pressure 1000 mb. No rain.
Temperature 15 degrees, pressure 990 mb. Rain.
Then the question is: 
Temperature 17 degrees, pressure 1010 mb. Will there be rain?
Explain your answer. What would the Hamming distance predict?

[6 marks]
1(d)   If we use units of 1000 mb (units of K mb) to measure pressure, so that, e.g., 1010 mb is written as 1.010 K mb, then will there be rain? What would the Hamming distance predict? [6 marks]
1(e)   What conclusion do you draw from the above?

[6 marks]

[Total marks: 30]
2(a)   Explain how Artificial Intelligence can be considered as a form of search. [5 marks]
2(b)   Briefly explain what a search approach to solving a problem would look like. [5 marks]
2(c)   Give an example of a simple form of heuristic search. [5 marks]
2(d)   In 1(c), give an example of where your heuristic search might converge to a local optimum rather than the global optimum. [5 marks]
2(e)   Give two examples of simple heuristics a human could use for mate search. Discuss how they could fail. [5 marks]
2(f)   Explain the concept of a metaheuristic. [5 marks]

[Total marks: 30]
3(a)   Explain "Algorithm A" (Best-first search with distance from start). [5 marks]
3(b)   In 1(a), explain how the "distance from start" component compensates for an inaccurate heuristic evaluation function.

[5 marks]
3(c)   Breadth-first search is admissible. Explain. [5 marks]
3(d)   Explain the concept of an A* algorithm. [5 marks]
3(e)   All A* algorithms are admissible. Explain. [5 marks]
3(f)   Explain that while it is in general easy to find an A* algorithm, it may be difficult to find an A* algorithm that is practical. [5 marks]

[Total marks: 30]
4(a)   Explain the concept of a genetic algorithm (GA). [5 marks]
4(b)   Describe the core algorithm of the genetic algorithm. List everything that needs to be defined precisely in order to code the algorithm. [5 marks]
4(c)   A Genetic Algorithm is search by "a population of hill-climbers". Explain. Why is this better than / different to search by a single hill-climber? [5 marks]
4(d)   In a genetic algorithm (GA), if the chromosome is a binary string of length n, what range of integers can this encode? [5 marks]
4(e)   In (d), how could you use this chromosome to encode a floating-point number in the range a to b? [5 marks]
4(f)   In (e), what does the length of the bitstring represent? [5 marks]

[Total marks: 30]

Bonus question (for 10 marks)

Tell me something interesting about human, animal, robot or computer intelligence that was not on the course.

CA318 - Advanced Algorithms and AI Search - Sample paper

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