Problem Definition:

Problem: Given an array of integers find all pairs of integers, a and b, where a b is equal to a given number.

For example, consider the following array and suppose we want to find all pairs of integers a and b where a b = 3

A = [10, 4, 6, 16, 1, 6, 12, 13]

Then your method should return the following pairs:

4, 1 15, 12 13, 10

A poor solution: There are several solutions to this problem. The most straightforward (but inefficient) solution is to set up a nested loop structure that goes over the elements of the array one by one and for each element performs a sequential search on the entire array. The running time for this algorithm is quadratic due to the nested loop structure and the sequential search for each array element.

Writing the straightforward inefficient solution will result in a 0. Utilize sorting (merge, quick, or radix sort) and searching to write an efficient algorithm. Becareful with which searching algorithm you choose. There is a way to write a linear search that will not devolve to the O(n²) efficiency, but one needs to be clever in how they approach this method. You may also utilize binary search which doesnt require one to be clever.

What you need to do for this assignment

When the size of the array is very large then the quadratic algorithm may be too slow to be useful. There are a number of strategies that can be employed to reduce the running time, and at this point we have covered enough topics to design a more efficient algorithm. Based on the material covered thus far in this course, design and implement a more efficient algorithm for this problem.

Your algorithm must on average have a running time of O(nlogn) where n is the number of elements in the array.

The framework for your algorithm should satisfy the following criteria:

1. Create a class called DifferencePairs, to contain your algorithm and associated methods and attributes.
2. In your DifferencePairs class, encapsulate your algorithm within a method called findPairs, with the signature:

public Pair[] findPairs(int array[], int diff)

3. The value returned by your findPairs method should be an array of Pair, where the difference between the first element and the second element in each pair in the array is equal to diff. If no such pair is found, then your method should return null.
4. You may use the codes from the textbook but you may not use the built-in search or sort method of other libraries. It is important that you adhere to the framework specification above to facilitate testing of your program.

Additional Information

1. Some utility methods have been given to you to help you. They can be found in assignment.utility.ArrayUtils class. These include
   1. printIntegerArray - This prints an array of integers to stdout.
   2. printObjectArray - This prints an array of arbitrary objects to stdout.
   3. truncateArray - This returns a truncated array of objects to keep while ignoring the rest.
2. A file of random numbers has been provided. Test your code with different diff values which you can change in the FileTest class. You may also change the values in the nums.txt file if you wish for testing.
3. A Pair class has been provided. Please do not modify the Pair class.
4. You may add additional methods in the DifferencePairs class.
5. YOU MAY NOT USE DYNAMIC DATA STRUCTURES SUCH AS ARRAYLISTS OR LINKEDLISTS OR ANY OTHER DYNAMIC DATA STRUCTURES. Your code should take an array and return an array.

What you need to turn in

1. Your DifferencePairs.java file (This should contain your findPairs method, as stated above and any additional method that you may use.
2. A .doc (or .rtf, .pdf, .txt, .docx) that contains two things

Briefly describe your algorithm and determine the time efficiency of it. Dont just say, for example, that my algorithm is O(nlogn), but explain how you got that time efficiency. Remember, dont evaluate your code. That takes too long and will give you a headache. Instead, try to conceptualize how you are solving the problem and determine the Big-O that way. Pen and paper will help with this.

3. Since there are several ways to solve the problem and multiple ways to interpret the solution you can submit either solution. Some students like to return only the unique pairs while others will return all pairs if there are duplicates of the same value in an array that match a given target. For instance, assume we have an array [1, 3, 5, 3, 1, 2, 3, 3] and the target is a difference of 2. You can return just the unique pairs which are Pair(1, 3) and Pair(3, 5) or you might return all pairs which would be Pair(1, 3), Pair(1, 3), Pair(1, 3), Pair(1, 3), Pair(3, 1), Pair(3, 1), Pair(3, 1), Pair(3, 1), Pair(1, 3), Pair(1, 3), Pair(1, 3), Pair(1, 3), Pair(3, 1), Pair(3, 1), Pair(3, 1), Pair(3, 1), and so on. What you return is up to you.

package assignment.diffpairs;

import assignment.utility.ArrayUtils;

public class DifferencePairs { // Implement your sorting algorithm here. Must be either // * merge sort // * quick sort // * radix sort private static void sort(int arr[]) { }

public static Pair[] findPairs(int array[], int diff) { return null; }

}

public class Pair { private int first; private int second; public Pair(int first, int last) { this.first = first; this.second= last; } public int getFirst() { return first; }

public int getSecond() { return second; }

public String toString() { return "(" + this.first + " , " + this.second+ ")"; } public boolean equals(Object other) { if(other == null) { return false; } if(!(other instanceof Pair)) { return false; } Pair otherPair = (Pair)other; return this.first == otherPair.first && this.second == otherPair.second; }

}

package assignment.utility;

import java.util.Arrays;

public class ArrayUtils {

public static void printIntegerArray(int arr[]) { if (arr == null) { System.out.println("null"); return; } System.out.print("[ "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i]); if (i < arr.length - 1) { System.out.print(", "); } } System.out.println(" ]"); }

public static void printObjectArray(Object arr[]) { if (arr == null) { System.out.println("null"); return; } System.out.print("[ "); for (int i = 0; i < arr.length; i++) { Object obj = arr[i]; System.out.print(obj.getClass().getName() + obj); if (i < arr.length - 1) { System.out.print(", "); } } System.out.println(" ]"); }

/** * This method takes a T array and the number of elements to truncate up to. * The result is a new T array with elements up to, but not including, count. * An example: * *

 * arr[] = [1,2,3,4,5,6] * truncateArray(arr, 3); * result: [1,2,3] * 

* * @param arr The array to truncate. * @param count The number of elements to keep. * @return A T array that is the truncated version of arr. */ public static T[] truncateArray(T arr[], int count) { if (arr == null) { throw new IllegalArgumentException("Truncate Array: The integer array must not be null"); } if (count > arr.length || count < 0) { throw new IllegalArgumentException("Count must be between 0 and the array length (inclusive)."); } return Arrays.copyOf(arr, count);