CA622 - Advanced Algorithms (Sample paper)

Answer 4 out of 6 questions. 25 marks each.

Question 1

1(a)	Explain how Artificial Intelligence can be considered as a form of search.	[5 marks]
1(b)	Briefly explain what a search approach to solving a problem would look like.	[5 marks]
1(c)	Give two examples of heuristic search algorithms. Briefly explain the algorithms.	[5 marks]
1(d)	Chess has a branching factor of about 35. The average length of a chess game is about 80 plies. Explain what these terms mean. Why do they mean that exhaustive search of chess is impossible?	[5 marks]
1(e)	If exhaustive search of the future moves of a chess game is impossible, what do chess programs do instead?	[5 marks]

[Total marks: 25]

Question 2

2(a)	Show with a diagram how the Xs and Os game can be represented as a State space Search problem.	[4 marks]
2(b)	In 2(a), how many paths through the graph are there?	[3 marks]
2(c)	In 2(a) and 2(b), is the number of paths the same as the number of states?	[3 marks]
2(d)	Could Xs and Os be solved by exhaustive search?	[3 marks]
2(e)	In Xs and Os, discuss how you could reduce the size of the search space by regarding separate states as equivalent to each other.	[4 marks]
2(f)	What are the problems in designing a heuristic evaluation function?	[4 marks]
2(g)	Explain how a heuristic evaluation function of: "Number of winning opportunities" would work in solving the Xs and Os problem. How would this reduce the search problem?	[4 marks]

[Total marks: 25]

Question 3

3(a)	Explain "Algorithm A" (Best-first search with distance from start).	[4 marks]
3(b)	In 3(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.	[4 marks]
3(d)	Explain the concept of an A^* algorithm.	[4 marks]
3(e)	All A^* algorithms are admissible. Explain.	[4 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.	[4 marks]

[Total marks: 25]

Question 4

4(a)	Explain the string searching problem. When might string searching be needed?	[3 marks]
4(b)	Describe the naive (brute force) algorithm for finding occurrences of a search pattern of size m in a text string of size n.	[3 marks]
4(c)	Give an example of how the naive (brute force) algorithm could be speeded up.	[4 marks]
4(d)	The UNIX command "grep" implements regular expressions in the search pattern. Explain why this causes difficulties for some string searching algorithms.	[3 marks]
4(e)	Explain the Knuth–Morris–Pratt string search algorithm.	[4 marks]
4(f)	In 4(e), explain how to build the table next[j].	[4 marks]
4(g)	In 4(f), draw the table next[j] for the search pattern "DOTSDOTT".	[4 marks]

[Total marks: 25]

Question 5

5(a)	Explain the concept of a genetic algorithm (GA).	[3 marks]
5(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]
5(c)	Why can the genetic algorithm not guarantee to find the global maximum?	[4 marks]
5(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 = 1? What would happen if p_m = 0 (but you still had crossover)? Should p_m change as the evolution proceeds?	[6 marks, 2 marks each]
5(e)	In 5(d), let p_c be the probability of crossover. What would happen if p_c = 1? What would happen if p_c = 0 (but you still had mutation)?	[4 marks, 2 marks each]
5(f)	In 5(d) and 5(e), what would happen if p_c = 0 and p_m = 0?	[3 marks]

[Total marks: 25]

Question 6

6(a)	In a genetic algorithm (GA), if the chromosome is a binary string of length n, what range of integers can this encode?	[2 marks]
6(b)	In 6(a), how could you use this chromosome to encode a floating-point number in the range a to b?	[3 marks]
6(c)	In 6(a) and 6(b), how could you encode a floating-point number from minus infinity to infinity in the finite length bitstring?	[3 marks]
6(d)	In 6(b) and 6(c), what does the length of the bitstring represent?	[2 marks]
6(e)	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". Consider the individuals: i 1 2 3 4 f(i) 0 0 0 1 Calculate the values p(i) if T=1. Calculate the values p(i) if T=10. Show that as `T -> infinity`, the individuals are all equally likely to reproduce.	[9 marks, 3 marks each]
6(f)	In 6(e), consider the individuals: i 1 2 3 4 f(i) 0.2 1 0.2 1 Calculate the values p(i) if T=1/5. What happens as `T -> 0`?	[6 marks, 3 marks each]

[Total marks: 25]