Question

Problem Definition: Problem: Given an array of integers find all pairs of integers, a and b,...

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.

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)

  1. 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.
  2. You may use the codes from the textbook or lab but you may not use the built-in search or sort method of other libraries. All code must be written by you!!!!

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.

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. Don’t just say, for example, that my algorithm is O(nlogn), but explain how you got that time efficiency. Remember, don’t 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.

  1. 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.

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;

}

}

Homework Answers

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
Recall the 2-sum problem which took an array of N integers and determined the number of...
Recall the 2-sum problem which took an array of N integers and determined the number of pairs that summed to 0. Now consider a 2-sum BST problem. Let B be a binary search tree with N integers as unique keys. Using only data structures and algorithms that have been discussed in this class, describe an algorithm that will return the number of pairs in B that add to 0. Analyze the space and runtime of your algorithm.
Given an array of integers return the sum of the values stored in the first and...
Given an array of integers return the sum of the values stored in the first and last index of the array. The array will have at least 2 elements in it --------------------------------------- public class Class1 { public static int endSum(int[] values) {     //Enter code here } }
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999,...
Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. You can use the following code template to obtain the execution time: long startTime = System.currentTimeMillis(); perform the task; long endTime = System.currentTimeMillis(); long...
Write recursive method to return true if a given array of integers, named numbers, with n...
Write recursive method to return true if a given array of integers, named numbers, with n occupied positions is sorted in ascending (increasing) order, or returns false otherwise. Array can be empty or not. //PRECONDITION: Varible n denotes the number of occupied positions in the array and must be non-negative. Employee class has method getSalary() that returns employee's salary. // An empty array and an array with single element in it, are sorted. Method isSortedRec must be recursive and returns...
Write a Java program that asks the user to enter an array of integers in the...
Write a Java program that asks the user to enter an array of integers in the main method. The program should prompt the user for the number of elements in the array and then the elements of the array. The program should then call a method named isSorted that accepts an array of and returns true if the list is in sorted (increasing) order and false otherwise. For example, if arrays named arr1 and arr2 store [10, 20, 30, 41,...
Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers...
Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers and sort it in-place. Write a program that generates random integer arrays (hint: use seed appropriately to avoid generating same sequences) of lengths 10, 100, 1000, 10,000, 100,000, 1000,000, and then sorts each using each of the sorting functions from (a), and measures the time in nanoseconds. The program will repeat this process 30 times and will compute the average execution time for each...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
You are asked to implement a C++ class to model a sorted array of unsigned integers....
You are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Your class should should: (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be...
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the...
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Requirements Implement the following functions: Implement a function called readData int *readData( )   The function returns a pointer that points to the locations with integers reading from the file data.txt. arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT