Skiena Chapter 4 Questions

End of chapter questions for Skiena Chapter 4.

Questions

Question 4.3

Take a sequence of real numbers 2n as input. Design an O(n log n) algorithm that partitions numbers into pairs, with the property that the partition minimizes the maximum sum of each pair.

Example: (1,3,5,9) can be split into three different partitions:

(1,3) (5,9) - sum of (4,14) - maximum of 14

(1,5) (3,9) - sum of (6,12) - maximum of 12

(1,9) (3,5) - sum of (10,8) - max of 10

Solution: To pair up numbers to minimize the sum, the largest element in the partition must be added to the smallest element in the array. Thus, we can solve the problem with two pointers to either end of an array, pairing up the largest number with the smallest number, the second-largest number with the second smallest number, and so on.

Step 1: Sort

Step 2: Create pairs from endpoints

x = sort(x)
for int in range 1 to n:
    index1 = i
    index2 = n - (i+1)
    new Pair(x[index1], x[index2])

Question 4.4

Given n pairs of items as inputs, 1st item is a number, 2nd item is a color, and items are sorted by number.

Give an O(n) algorithm to sort the items by color, such that the numbers for identical colors remain sorted.

Example: (1 Blue) (3 Red) (4 Blue) (6 Yellow) (9 Red) becomes (3 Red) (9 Red) (1 Blue) (4 Blue) (6 Blue)

Solution: Let's focus on an algorithm to sort by color, first, then focus on keeping the numbers sorted afterwords.

This is an example of what's called the Dutch national flag problem, originally proposed by Edsger Dijkstra. The challenge is to sort a random array of objects falling into three classes in O(n) time. We do this by putting one class of items at the front of the bucket, one class of items at the end of the bucket, and ignoring the rest (which will all end up in the middle).

The algorithm has a similar look and feel to merge sort.

Here's a detailed explanation of the step by step:

• Start at the beginning - create a RED pointer to the spot where the next red item will go, and BLUE to the spot where the next blue item will go. I put RED in the back and BLUE at the front. Note that these should not necessarily point to blue or red elements, they simply point to the next location a blue or red item will go when one is encountered.
• Create a walker pointer that will walk the length of the array, until it encounters the RED pointer. Here is what it does while it has not hit RED:
  • if walker points to a blue record, swap it with the BLUE pointer and move BLUE up by one
  • else if walker points to a red record, swap it with the RED pointer and move RED up by one
  • else increment walker by one

Question 4.5

The mode of a set of numbers is the number that occurs the most frequently. Example: (4, 6, 2, 4, 3, 1) ahs mode of 4. Give an algorithm to compute the mode of a set of n numbers.

Solution: Three possible approaches (one special case):

• Faster solution using more space: use a hash table to keep track of object counts
• Slower (less storage space/in-place) solution: sort and find runs
• Special case: integers are 0 or 1 to n, then we can use the hash table approach except use an array instead of a hash table, with the integers acting as their own keys

Here is an implementation of the hash map solution:

public static int getMode(List<Integer> s) { 
	Map<Integer, Integer> m = new HashMap<Integer, Integer>();
	int mode = SENTINEL, modeCount = 0;
	for(Integer n : s) { 
		if(m.contains(n))  {
			Integer i = m.get(n);
			i += 1;
			if(i>modeCount){  
				mode = n;
			}
		} else {
			m.put(n,1);
		}
	}
	return mode;
}

Alternatively, here is an implementation of the longest run idea:

public static int getMode(List<Integer> s) { 
	Collections.sort(s);
	int mode = SENTINEL;
	int longestRun = 0, currentRun = 0;
	for(int i=1; i<s.length; i++) { 
		if(s.get(i).equals(s.get(i-1)) {
			currentRun++;
			if(currentRun > longestRun) {
				mode = s.get(i);
			}
		} else {
			currentRun = 0;
		}
	}
	return mode;
}

Note that both solutions implement a SENTINEL value as the initial mode, so that if the SENTINEL is returned, we know something went wrong.

Question 4.7

Outline a reasonable method for each scenario:

a) A pile of bills a pile of checks - figure out who did not pay.

Start by sorting the list of people who have paid with checks. Now you have two lists, and you are looking for the RELATIVE COMPLEMENT - the elements in Bills that are not also in Checks. We will assume, for simplicity, that there is no charity, i.e., all check names are in bill names). Then our list looks like this:

Checks: ## # # #### # # #### #####
Bills:  ##########################

Now we can iterate through bill names (either sorted or unsorted) and perform a binary search for each name in checks to figure out which names are missing from checks. As we iterate through bills and find missing names, we add them to a running list.

A little psuedo-Java-ish-code, assuming we're dealing with a queue of Strings (alternatively, we might have a list of Record items, in which case we're sorting using the name attribute as the key):

while(!bills.isEmpty()) { 
	owes = bills.remove();
	if(checks.peek() == owes) {
		paid = checks.remove();
		nice.add(paid);
	} else {
		naughty.add(owes);
	}
}