A well explained answer will be appreciated and sincerely liked.........

Thank you in advance............

Exercise 1:

Solve the recurrence relation

An = -8 An-1 16 An-2

or the initial condition given.

A0 =2 A1 = -20

Exercise 2:

Let consider to the sequence

S1 = C, S2= G, S3 = J, S4 = M, S5 = X

Refer to the sequence S to show how the algorithm of the binary search executes in case

key = G.

Algorithm: The binary search:

Input: A sequence Si, Si+1, , Sj, i 1, sorted in nondecreasing order, a value key, i and j.

Output: The output is an index k fro which Sk = key, or if key is not in the sequence, the output is the value 0.

1. Binary_search(S, i, j, key) {

2. if (i > j) // not found

3. return 0

4. k = |_(i + j)/2_|

5. if (key ==Sk) // found

6. return k

7. if (key < Sk) // search left half

8. j = k - 1

9. else // search right half

10. i = k + 1

11. return binary_search(S, i, j, key)

12. }

Exercise 3:

Professor Larry proposes the following version of binary search:

binary_search3(s, i, j, key){

while ( i j) {

k = |_(i+j)/2_|

if (key==Sk)

return k

if (key < Sk)

j = k

else

i = k

}

return 0

}

Is professors version correct (does it find key if it is present and return 0 if it is not present? If the professors version is correct, what is the worst-case time?