[Python]

We are given input file in.txt that has number K and sequence of N numbers. We want to determine if there are two numbers whose sum equals a given number K. For instance, if the input file is

SumOfK

10

8416

We know from the file that K is 10, sequence of numbers is 8 4 1 6, and number of elements N is 4 (we can count numbers)

For given information then the answer is yes (4 and 6), because 4+6 is 10. A number may be used twice. If input file is SunOfK

10 8453 the answer is also yes, because 5+5 is 10

Do the following:

Algorithm 1 : Give an O(N2) algorithm to solve this problem. Algorithm 2: Give an O(N*log(N)) algorithm to solve this problem. (Hint: Sort the items first. After that is

done, you can solve the problem in linear time.)

https://en.wikipedia.org/wiki/Heapsort

Code both solutions and compare the running times of your algorithms. Get input from input file in.txt Print output to output file out.txt

For input in.txt

10 8416

Output file has to have:

Algorithm1: 8416 Yes 4+6=10 Algorithm2: 1 4 6 8

Yes

4+6=10

//sorted

//calculation time in nanoseconds for both algorithms

For input in.txt

10 8453

Output file has to have:

Algorithm1: 8453 Yes 5+5=10 Algorithm2 3 4 5 8 //sorted Yes

5+5=10

//calculation time in nanoseconds for both algorithms

For input in.txt

11 8451

Output file has to have:

Algorithm1

8451

No Algorithm2 1 4 5 8 //sorted No //calculation time in nanoseconds for both algorithms