Algorithm Question:

Please do not write a real program.

The answer should be an explaination of your algorithm or pseudocode. Try to answer clearly and concisely. Thank you very much. I will upvote all answers.

This is a multipart algorithm question:

(a) Given an array A and a number z, write an efficient algorithm that checks if there are two indices 1 i < j n, so that A[i] + A[j] = z.

(b) Solve this question of A[i] + A[j] = z if the array is sorted. Explain why your algorithm works

(c)Solve the same problem via a randomized algorithm. Make the expected running time as small as possible.