1. Assume that you are given two lists A, B of the same size, n, of positive and

Question

1. Assume that you are given two lists A, B of the same size, n, of positive and negative integer values. The problem is to find all the pairs of values, (a, b), a from A, b from B, such that a + b = 0. Describe an algorithm of complexity O(nlogn) which solves this problem. Note that it is easy to write a O(n2) algorithm.

2. Next consider that you have k = 3, 4 such lists. For example, for k=3, this problem, means that you are given three lists and you are looking for triplets (a, b, c) such that a+b+c = 0, for k = 4, that you are given four such lists and you are looking for quadruples (a, b, c, d) such that a+b+c+d = 0. Discuss the generalization of your algorithm for k=3, 4. Can it be generalized? If yes, show how, and prove the behavior of your algorithm, that is find its O(f(n)) for some f(n). If you think that your solution cannot be generalized, explain why not.

Explanation / Answer

1.

use sorting.

sort both the arrays and take the starting element of the array from arr1 and last element from arr2.

if (arr1+arr2 > 0) then decrement the value in arr2 else increment the value in arr1 if (arr1+arr2 < 0). if in the iterations (arr1+arr2=0) then you have found the pair.

Use merge sort/heap sort to sort the array. compleity will be O(nlogn)

2)

This solution cannot be generalises as it is valid only for 2 lists. The common n2 approach can be used to get the correct solution.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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