Week 3: Randomness and Local Search Methods

Question 1

WITNESS

Answer 1

This is a protocol for checking whether two different sequences of bits, x and y of length n, are the same or different.

A random prime number is chosen in the range of 2 to n^2. The modulo of this number is performed on x and y. If the modulos are identical, then x and y are reported as being the same. Otherwise, they’re reported as being different.

If x and y are indeed the same, WITNESS always correctly identifies them as the same. If x and y are different, there’s a chance WITNESS accidentally identifies them as being the same.

Question 2

Miller Rabin Test

Answer 2

This test helps find prime numbers. If the candidate number is composite, the test always identifies it as a composite number. If the candidate number is a prime number, the test has up to a 50% chance of finding that it’s a prime number.

Question 3

Energy Landscape

Answer 3

This is the feature space R with all possible configurations and their values.

Question 4

Local Optimum

Answer 4

A configuration is a local optimum if it’s less than or equal to all other configurations in its neighbourhood.

Question 5

Global Optimum

Answer 5

A configuration is a global optimum if it’s less than or equal to all configurations in R.

Question 6

Plateau

Answer 6

A configuration is in a plateau if its equal to all of its neighbours.