Algorithm Question: Please do not write a real program. The answer should be an

Question

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.

Explanation / Answer

CHEGG POLICY: ONLY ONE QUESTION PER POST IS ALLOWED

function( A<-n , z)

1)Initialize exist = False

2)for j in range(n)

3) for i in range(j)

4)       if A[i] + A[j] == z

5) then exist = True

6) return exist

Step1: Initialize the variable exist to False

Step2: Loop j through all index of the array

Step3: Inside loop create another loop i that goes till j

Step4: Check if A[i] + A[j] == z

Step5: if yes then assign True to the variable exist

Step6: return exist

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.