Programming Task 2. The input consists of n numbers a1, a2, . . . , an. The goal is to determine a value t that can be obtained by adding two of these numbers and, moreover, the number of pairs of these numbers that add up to t is the largest possible (in other words, you need to find the most popular sum of two numbers in the list). Formally, your program will find a t such that the size of the set {(i, j) | i < j, ai+aj = t} is maximum among all possible t’s. For example, for 2, 7, 3, 1, 5, 6, we have: 2 + 6 = 7 + 1 = 3 + 5. This is the largest number of pairs that sum to the same number, and, therefore, t = 8. Describe an O(n 2 log n) algorithm for this problem, and implement it in Java or C++. (For an example of what I mean by “Describe …,” see the NOTE 2 at the end of this document). You must explain clearly why your algorithm runs in O(n 2 log n) time. Hint: The number of pairs (ai , aj ) with i < j is n 2
= n(n − 1)/2 = Θ(n 2 ), and so you can afford to consider all these pairs. Input specification: The input consists of two lines. The first line contains a positive integer n. The second line contains integers a1, a2, . . . , an, separated by spaces. You may assume that the input integers fit in int. You may also assume that n is positive and not larger than 10,000. Output specification: the output contains a single line with the number t. If there are multiple possibilities for t, output the smallest one. Sample inputs (see files) : input-2.1.txt input-2.2.txt Sample outputs : answer2.1.txt answer-2.2.txt Test your program on the following inputs: input-2.4.txt input-2.6.txt and report the results you have obtained. NOTE 2: You can find an example of what I mean by “Describe an algorithm …” at https://www.geeksforgeeks.org/find-the-element-tha…

DETAILED ASSIGNMENT

20200926190701input