Given a sorted array A of n (possibly negative) distinct integers, an equilib- rium point is defined to be an index i such that A[i] = i. The array is indexed starting from 1. (a) (2pt) Consider two arrays: A = (2,3,4,5) and A = (5,4,3,12). Which of the following is correct? For the one that is correct, what are the equilibrium points of A and/or A? (a) A has an equilibrium point and A does not (b) A does not have an equilibrium point and A does. (c) A and A both have an equilibrium point (b) (2pt) Consider the array A = (?,?,?,5,?,?,?,?) of size n = 8. Here, ? denotes a hidden value; however, you know that A[n/2] = 5. Give the missing values of A such that there exists an equilibrium point. Remember that A must be sorted and cannot repeat values. (c) (2pt) Again, consider the array A = (?,?,?,5,?,?,?,?) of size n = 8. Is it possible for the equilibrium point to lie in A[5..8]? Either give an example showing it is possible or explain why it is not possible. Remember that A must be sorted and cannot repeat values. (d) (6pt) Describe a divide-and-conquer algorithm to decide if A contains an equilibrium point. You should aim for an algorithm that will run in time O(log n). You can assume that n is a power of 2 for simplicity. Your description can be in plain English, though we will also accept pseudo-code. (e) (4pt) Analyze the running time of your algorithm. In other words, argue why your algorithm has a running time of O(log n). If your algorithm has a different running time, you should argue why it has that running time.

(16 pts.) Equilibrium point: Given a sorted array A of n (possibly negative) distinct integers, an equilibrium point is defined to be an index i such that A[i]=i. The array is indexed starting from 1 . (a) (2pt) Consider two arrays: A=(2,3,4,5) and A=(5,4,3,12). Which of the following is correct? For the one that is correct, what are the equilibrium points of A and/or A ? (a) A has an equilibrium point and A does not (b) A does not have an equilibrium point and A does. (c) A and A both have an equilibrium point (b) (2pt) Consider the array A=(?,?,?,5,?,?,?,?) of size n=8. Here, "?" denotes a hidden value; however, you know that A[n/2]=5. Give the missing values of A such that there exists an equilibrium point. Remember that A must be sorted and cannot repeat values. (c) (2pt) Again, consider the array A=(?,?,?,5,?,?,?,?) of size n=8. Is it possible for the equilibrium point to lie in A[5.8] ? Either give an example showing it is possible or explain why it is not possible. Remember that A must be sorted and cannot repeat values. (d) (6pt) Describe a divide-and-conquer algorithm to decide if A contains an equilibrium point. You should aim for an algorithm that will run in time O(logn). You can assume that n is a power of 2 for simplicity. Your description can be in plain English, though we will also accept pseudo-code. (e) (4pt) Analyze the running time of your algorithm. In other words, argue why your algorithm has a running time of O(logn). If your algorithm has a different running time, you should argue why it has that running time