- This question paper is composed of 5 pages containing five questions. - Please

Question

- This question paper is composed of 5 pages containing five questions. - Please read the whole paper before starting to answer - You have ten minutes to read the paper and then only twenty minutes to ask questions. - The only questions allowed concern the spelling and the meaning of English words - Intermediate reasoning steps are demanded. Any unjustified answer is not accepted - Remember to write down you're your full name and your student id number Question One 120 marks] Assume you are given a number X and two sorted lists of n number each. A;

Explanation / Answer

Pseudocode:

int numPair(A,B,n)

count = 0

last_index = n

while (last_index != 0 && first_index != n+1)

if (A[first_index] + B[last_index] <= X)

count = count + last_index //last_index gives the number of elements from list B which when added

//to A[first_index] results in a number <= X

first_index++;

else //it means the sum is gretaer than X for A[first_index] + B[last_index].So we have to reduce last_index

// by 1 because A[x] + B[y] >X for all x > first_index and for all y > last_index

last_index--;

return count

Proof of O(n):

Since in the while loop one either last_index gets decremented by 1 or first_index gets incremented by 1.

So last_index will take n iterations to become 0 from n and first_index will take n iterations to become n+1 from 1

So there will be 2*n iterations of while loop which is of Order(n).

Correctness:

In each iteration we check whether A[first_index]+B[last_index] <=X.

If it is not so then we decrease last_index by 1.Because  if A[first_index]+B[last_index] > X then A[first_index]+B[y] > X for all y > last_index because B[y]>= B[last_index] for all y > last_index. So there is not need to compare them.

But if A[first_index]+B[last_index] <=X then A[first_index] + B[y] <= X for all y <=last_index because B[y]<=B[last_index] for all y <=last_index.So there will be last_index number of elemets whos sum with A[first_index] <=X . So there is no need to check the addition of A[first_index] with B[y] where y < last_index.Thats why we increase first_index by 1.

So, count will store the number of elements from B whose sum with A[i] <=X for 0<= i <=n.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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