## CPSC 327, Spring 2018 Some Sample Answers to Homework 6

### Problem 1

The problem is to merge K sorted lists.

(a) In the obvious algorithm, we build a sorted list by merging the K sorted lists in one pass. The idea is to look at the first element in each (non-empty) list and choose the list that contains the smallest first element. Move that element from the list that contains it, to the end of the merged list. Finding the minimum item among the first items in the K lists takes K−1 steps (or fewer after some of the lists become empty). This is done for each of the N items in the lists, for a total run time of Θ(N*K) in the worst case.

(b) To use a priority queue, we can put the K lists into a priority queue, using the first item in a list as its key. (We want to use a priority queue that produces the minimum value of the keys rather than the maximum value.) The idea then is to get the top list from the heap, remove its first item and add it to the merged list, and then re-insert the list into the heap (if it is non-empty). Removing and inserting an item takes time Θ(log(K)), and this is done for each of the N items. So the run time is now Θ(N*log(K)). In pseudocode:

```        merged = an empty list
queue = an empty priority queue of lists
for each of the original lists
while ( ! queue.isEmpty() )
l = queue.remove()
x = l.removeFirst()
if ( ! l.isEmpty() )
```

### Problem 2

A working program for the Dutch national flag problem (using 1, 2, and 3 instead of red, white, and blue) is given below. This could be applied to Quicksort by using the same idea in the Quicksort partition algorithm, to rearrange array elements into three groups, the first with keys less than the pivot, the second with keys equal to the pivot, and the third with keys greater than the pivot. This would improve the performance of Quicksort for arrays that have large numbers of duplicate keys, where the standard partitioning algorithm would run into trouble. (Another idea for solving the same problem would be to use the standard partitioning algorithm, but when encountering a key equal to the pivot, decide randomly whether to place that item above or below the final position of the pivot.)

```        /** Implements and tests a partitioning algorithm that
*  sorts an array containing only three different values
*  (1, 2, and 3) in run time proportional to the array length.
*/
public class BWR {

public static void main(String[] args) {
int A[] = new int[10000];
for (int i = 0; i < A.length; i++)
A[i] = 1 + (int)(3*Math.random());
int[] B = A.clone();
java.util.Arrays.sort(B);
partition(A, 0, A.length-1);
for (int i = 0; i < A.length; i++) {
//System.out.println(A[i] + " " + B[i]);
if (A[i] != B[i]) {
System.out.println("Error at position " + i);
return;
}
}
System.out.println("worked");
}

static void partition( int[] A , int lo, int hi ) {
// rearrange the array into sorted order
int b = lo;
int r = hi;
int w;
for (w = lo; w <= r;) {
if (A[w] == 1) {
swap(A, b, w);
b++;
w++;
}
else if (A[w] == 3) {
swap(A, r, w);
r--;
}
else {
w++;
}
}
System.out.printf("b = %d   w = %d   r  = %d%n", b, w, r);
}

static void swap( int[] A, int a, int b ) {
int temp = A[a];
A[a] = A[b];
A[b] = temp;
}

}
```

### Problem 3

(a) There are sqrt(N) items that still need to be inserted into their correct postions. This could involve moving on the order of N items (as many as N−sqrt(N) items moved for the first item in the unsorted part of the array, and up to N items moved for the last item in the array). So the total run time in the worst case would be Θ(N*sqrt(N)).

(b) A better idea would be to sort the sqrt(N) unsorted items using, for example, heap sort or merge sort. The run time to sort sqrt(N) items would be Θ(sqrt(N)*log(sqrt(N))), which reduces to Θ(sqrt(N)*log(N)) since log(sqrt(N)) = (1/2)*log(N). We would then have two sorted segements in the array: the first N−sqrt(N) items and the last sqrt(N) items. These can be merged in time Θ(N). The total run time is then Θ(N + sqrt(N)*log(N). At this point, you have to notice that N >> sqrt(N)*log(N), so the total run time reduces to Θ(N).

### Problem 4

(a) Here is a subroutine that answers the question in time Θ(N).

```          boolean sumExists(int[] A, int sum) {
if (A.length < 2)
return false;
int lo = 0;
int hi = A.length-1;
while (true) {
while ( hi > lo && A[hi] + A[lo] > sum )
hi--;
if (hi == lo)
return false;
if (A[lo] + A[hi] == sum)
return true;
lo++;
if (hi == lo)
return false;
}
}
```

The loop invariant here is that "if there are indices i and j such that A[i]+A[j] == sum, with i < j then lo <= i < j <= hi.

Note that this implies that when hi == lo, no such indices can exist and therefore the return value of false is correct for that situation. Also, when A[lo]+A[hi] == sum the return value true is also correct (given that at that point in the algorithm, we also know hi != lo, so that lo and hi are in fact two different indices). So why is the loop invariant always true?

The loop invariant is true before the outer while loop, since at that point all possible indices are in the range lo through hi. If A[hi]+A[lo] > sum, then since the array is sorted, then for any k > hi, A[k]+A[lo] is not smaller than A[hi]+A[lo] and so it is also true that A[k]+A[lo]>sum. This means that we can safely do hi-- without changing the truth of the loop invariant. At the end of the loop, where we do lo++, we know that A[lo]+A[hi] < sum, and since the array is sorted, then for any k < lo, A[k]+A[hi] is no bigger than A[lo]+A[hi] and so it is also true that A[k]+A[hi] < sum. So incrementing lo does not change the truth of the loop invariant. Since the loop invariant starts out true, and its truth doesn't change, the value returned by the subroutine will always be correct. Furthermore, the subroutine does not have an infinite loop since hi is always decremented in the nested while loop and lo is always incremented in the outer loop.

(b) The algorithm is to sort the array in time Θ(N*log(N)) and then apply the procedure from part a.

### Problem 5

The algorithm uses the same partitioning algorithm as in Quicksort. However, one the partitioning has been applied, we can tell simply by testing the final postion of the pivot whetcher the k-th smallest element is in the section preceding the pivot or in the section following the pivot.

```        int kthSmallest(int[] A, int k) {
// precondition: 0 <= k < A.length
int lo = 0;
int hi = A.length-1;
while (hi > lo) {
// loop invariant:   lo <= k <= hi
int mid = partition(A, lo, hi);
if (mid == k)
return A[mid];
else if (mid > k)
hi = mid - 1;
else // mid < k
lo = mid + 1;
}
return A[lo];
}
```

To see why this might have run time Θ(N), suppose that the partitioning always divides the remaining range lo to hi approximately in two. In that case the number of items between lo and hi is N originally, about N/2 after one execution of the while loop, N/4 after two executions, N/8 after 3, N/16 after 4, and so on. Partitioning K items takes K steps, so the total run time would be about N + N/2 + N/4 + N/8 + N/16 + ..., and this adds up to about 2*N. Of course, as with Quicksort, the worst case run time is bad.

### Problem 6

A Java method for sorting an array of ints, where all the values in the array are in the range 0 to K-1:

```        void sortByCounting(int[] A, int K) {
int[] C = new int[K];  // C[i] is the number of i's in A
for (int x : A)
C[x]++;
int[] S = new int[K];  // S[i] is position of first i in sorted array
for (int i = 1; i < K; i++)
S[i] = S[i-1] + C[i-1];
int[] B = new int[A.length];    // sorted copy of A
for (int x : A)
B[ S[x]++ ] = x;   // Now, S[x] is the position of NEXT x to be added to B
for (int i = 0; i < A.length; i++) // Copy B to A
A[i] = B[i];
}
```

Two of the four for loops run for N iterations (where N is A.length), and the other one runs K times. We also create two arrays of size K and one of size N. Assuming that array creation takes time proportional to the length of the array, the total run time is Θ(N+K). If K is O(N), then Θ(N+K) reduces to Θ(N).

### Problem 7

We have a file on disk that is too big to fit into RAM, but we still want to use RAM efficiently. Suppose that we have enough RAM to load 1/K times the length of the file into RAM and sort it, where K is a positive integer. So, run a loop in which we read the file in K sections, sort each section, and write the sorted results into K new files. We now have K sorted files on disk, and the original file can be deleted. To complete the sort, we need to merge the K files into one large sorted file that contains all the data. To merge the files, we can procede similarly to merge sort: Pair up the files and merge each pair of files into a longer file (deleting the two original files after they have been merged). We then have K/2 sorted files. Then in the next phase, pair up the K/2 files and merge each pair, leaving K/4 sorted files. After the next phase, there will be K/8 files, then K/16, and so on. We will be done after log2(K) phases.

If the original file contains B blocks, then during the first step (reading the original file and creating the K sorted files), we read all B blocks from the original file and write B blocks to the output file. Then in each phase of the merging process, we again read read and write all of the data, so that each phase involves reading and writing B blocks. Since there are log2(K) phases, the total number of blocks read during the merge part of the process is B*log2(K). Adding in the B blocks read in the first step of the algorithm, the total number of blocks read is about B*(1+log2(K)). The same number of blocks is written.

(Note: To merge two files, open the files and open an output file. Read the first item from each file. Then repeat: Write the smaller of the two items to the output file; if the input file where that item came from is empty, copy the rest of the other file to the output and end; otherwise, read a new item from that input file.)

### Problem 8

Here is a link to my Quicksort program. I did not get great results. My version is a little faster than Arrays.sort for random arrays. (That's when I ran it with the just-in-time compiler enabled; when run without the compiler, my version took twice as long as Arrays.sort.) However, Arrays.sort was much better on a sorted array and on an array with lots of duplicates. Worse, the basic recursive Quicksort that we started with was faster than my improved version on a random array (although, of course, it's very bad for a sorted array).