THE ALGORITHM DESIGN MANUAL PROBLEM 4-2

For each of the following problems, give an algorithm that finds the desired
numbers within the given amount of time. To keep your answers brief, feel free to
use algorithms from the book as subroutines. For the example, S = {6, 13, 19, 3, 8},
19 − 3 maximizes the difference, while 8 − 6 minimizes the difference.
(a) Let S be an unsorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(n) worst-case time.
(b) Let S be a sorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1) worst-case time.
(c) Let S be an unsorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in O(n log n)
worst-case time.
(d) Let S be a sorted array of n integers. Give an algorithm that finds the pair
x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in O(n)
worst-case time.

package avdongre.adm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * For each of the following problems, give an algorithm that finds the desired
 * numbers within the given amount of time. To keep your answers brief, feel
 * free to use algorithms from the book as subroutines. For the example, 
 * S = {6, 13, 19, 3, 8}, 19 − 3 maximizes the difference, while 8 − 6 minimizes the
 * difference.
 * 
 * (a) Let S be an unsorted array of n integers. Give an algorithm that finds
 * the pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(n)
 * worst-case time.
 * 
 * (b) Let S be a sorted array of n integers. Give an algorithm that finds the
 * pair x, y ∈ S that maximizes |x − y|. Your algorithm must run in O(1)
 * worst-case time.
 * 
 * (c) Let S be an unsorted array of n integers. Give an algorithm that finds
 * the pair x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run
 * in O(n log n) worst-case time.
 * 
 * (d) Let S be a sorted array of n integers. Give an algorithm that finds the
 * pair x, y ∈ S that minimizes |x − y|, for x = y. Your algorithm must run in
 * O(n) worst-case time.
 * 
 * @author adongre
 *
 */
public class MaxMinVariations {
	private class Pair {
		public int first;
		public int second;
		public Pair(int x, int y ) {
			first = x;
			second = y;
		}
		@Override
	    public String toString() {
	        return String.format(first + "," + second);
	    }
	}
	private int [] generateInputArray(int size) {
		ArrayList<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i < size; i++) {
			list.add(new Integer(i));
		}
		Collections.shuffle(list);
		int[] result = new int [ list.size()];
		for (int i = 0; i < list.size(); i++) {
			result[i] = list.get(i).intValue();
		}		
		return result;
	}
	public Pair getMaxPairFromUnsortedArray(int [] input) {
		if ( input == null) {
			return null;
		}
		int largest = Integer.MIN_VALUE;
        int smallest = Integer.MAX_VALUE;
		for ( int i = 0; i < input.length; i++) {
			if (input[i] > largest) {
                largest = input[i];
            } else if (input[i] < smallest) {
                smallest = input[i];
            }
		}
		Pair p = new Pair(smallest, largest);
		return p;		
	}
	public Pair getMaxPairFromSortedArray(int [] input) {
		if ( input == null) {
			return null;
		}
		Arrays.sort(input);
		Pair p = new Pair(input[0], input[input.length - 1]);
		return p;		
	}
	
	public Pair getMinPairFromUnsortedArray(int [] input) {
		if ( input == null) {
			return null;
		}
		if ( input.length < 2) {
			return null;	
		}
		Arrays.sort(input);
		int smallest = 0;
		int largest = 0;
		int currentMinimum =  Integer.MAX_VALUE;
		for ( int i = 1; i < input.length; i++) {
			if ( currentMinimum > (input[i] - input[i-1])) {
				currentMinimum = input[i] - input[i-1];
				smallest = input[i -1];
				largest = input[i];
			}
		}
		Pair p = new Pair(smallest, largest);
		return p;		
	}
	public Pair getMinPairFromSortedArray(int [] input) {
		if ( input == null) {
			return null;
		}
		if ( input.length < 2) {
			return null;	
		}
		Arrays.sort(input);
		int smallest = 0;
		int largest = 0;
		//Pair p = new Pair(input[0], input[1]);
		int currentMinimum =  Integer.MAX_VALUE;
		for ( int i = 1; i < input.length; i++) {
			if ( currentMinimum > (input[i] - input[i-1])) {
				currentMinimum = input[i] - input[i-1];
				smallest = input[i -1];
				largest = input[i];
			}
		}		
		Pair p = new Pair(smallest, largest);
		return p;
	}
	
	
	public static void main(String[] args) {
		MaxMinVariations mm = new MaxMinVariations();
		{
			int [] inputArray = mm.generateInputArray(10);
			System.out.println(Arrays.toString(inputArray));
			System.out.println(mm.getMaxPairFromUnsortedArray(inputArray));
		}
		{
			int [] inputArray = mm.generateInputArray(10);
			System.out.println(Arrays.toString(inputArray));
			System.out.println(mm.getMaxPairFromSortedArray(inputArray));
		}
		{
			int [] inputArray = mm.generateInputArray(10);
			System.out.println(Arrays.toString(inputArray));
			System.out.println(mm.getMinPairFromUnsortedArray(inputArray));
		}		
		{
			int [] inputArray = mm.generateInputArray(10);
			System.out.println(Arrays.toString(inputArray));
			System.out.println(mm.getMinPairFromSortedArray(inputArray));
		}	
		{
			int [] inputArray = new int[] {5,10,11,12};
			System.out.println(Arrays.toString(inputArray));
			System.out.println(mm.getMinPairFromSortedArray(inputArray));
		}	
	}

}

Advertisements

One thought on “THE ALGORITHM DESIGN MANUAL PROBLEM 4-2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s