Skiena Chapter 4 Questions - Revision history

Admin: /* Question 4.7 */

2017-07-16T10:59:05Z

Question 4.7

← Older revision		Revision as of 10:59, 16 July 2017
Line 118:		Line 118:
	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.		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:		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):

	<pre>		<pre>

Admin: /* Question 4.5 */

2017-07-16T10:58:17Z

Question 4.5

@@ Line 102: / Line 102: @@
 Note that both solutions implement a SENTINEL value as the initial mode, so that if the SENTINEL is returned, we know something went wrong.
 =Flag=
 {{AlgorithmsFlag}}

Admin: /* Question 4.4 */

2017-07-16T10:52:42Z

Question 4.4

@@ Line 50: / Line 50: @@
 ** else increment walker by one
 =Flag=
 {{AlgorithmsFlag}}

Admin: Created page with "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..."

2017-07-16T10:27:41Z

Created page with "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..."

New page

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

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

===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

=Flag=

{{AlgorithmsFlag}}