4.2 Sorting and Searching

This section under construction.

The sorting problem is to rearrange a set of items in ascending order. One reason that it is so useful is that it is much easier to search for something in a sorted list than an unsorted one. In this section, we will consider in detail two classical algorithms for sorting and searching, along with several applications where their efficiency plays a critical role.

Twenty questions

Binary search.

In the game of "twenty questions", your task is to guess the value of a hidden number that is one of the N integers between 0 and N-1. (For simplicity, we will assume that N is a power of two.) Each time that you make a guess, you are told whether your guess is too high or too low. An effective strategy is to maintain an interval that contains the hidden number, guess the number in the middle of the interval, and then use the answer to halve the interval size. TwentyQuestions.java implements this strategy, which is an example of the general problem-solving method known as binary search.

Correctness proof. First, we have to convince ourselves that the method is correct: that it always leads us to the hidden number. We do so by establishing the following facts:
- The interval always contains the hidden number.
- The interval sizes are the powers of two, decreasing from N.
The first of these facts is enforced by the code; the second follows by noting that if the interval size (hi-lo) is a power of two, then the next interval size is (hi-lo)/2, which is the next smaller power of two. These facts are the basis of an induction proof that the method operates as intended. Eventually, the interval size becomes 1, so we are guaranteed to find the number.
Running time analysis. Since the size of the interval decreases by a factor of 2 at each iteration (and the base case is reached when N = 1), the running time of binary search is lg N.
Linear-logarithm chasm. The alternative to using binary search is to guess 0, then 1, then 2, then 3, and so forth, until hitting the hidden number. We refer to such an algorithm as a brute-force algorithm: it seems to get the job done, but without much regard to the cost (which might prevent it from actu- ally getting the job done for large problems). In this case, the running time of the brute-force algorithm is sensitive to the input value, but could be as much as N and has expected value N/2 if the input value is chosen at random. Meanwhile, binary search is guaranteed to use no more than lg N steps.
Binary representation. If you look back to Program 1.3.7, you will recognize that binary search is nearly the same computation as converting a number to binary! Each guess determines one bit of the answer. In our example, the information that the number is between 0 and 127 says that the number of bits in its binary representation is 7, the answer to the first question (is the number less than 64?) tells us the value of the leading bit, the answer to the second question tells us the value of the next bit, and so forth. For example, if the number is 77, the sequence of answers no yes yes no no yes no immediately yields 1001101, the binary representation of 77.

Bisection search

Inverting a function. As an example of the utility of binary search in scientific computing, we revisit a problem that we consider the problem of inverting an increasing function. To fix ideas, we refer to the Gaussian distribution Φ when describing the method. Given a value y, our task is to find a value x such that Φ(x) = y. In this situation, we use real numbers as the endpoints of our interval, not integers, but we use the same essential method as for guessing a hidden integer: we halve the size of the interval at each step, keeping x in the interval, until the interval is sufficiently small that we know the value of x to within a desired precision δ. We start with an interval (lo, hi) known to contain x and use the following recursive strategy:
- Compute m = lo + (hi - lo) / 2
- Base case: If (hi - lo) is less than δ, then returm m as an estimate of x
- Recursive step: otherwise, test whether Φ(m) < y. If so look for x in (lo, m); if not look for x in (m, hi)
The key to this method is the idea that the function is increasing - for any values a and b, knowing that Φ(a) < &Phi(b) tells us that a < b, and vice versa. In this context, binary search is often called bisection search because we bisect the interval at each stage.
Binary search in a sorted array. During much of the last century people would use a publication known as a phone book to look up a person's phone number. Entries appears in order, sorted by a key that identifies it (the person's name) n both cases). A brute-force solution would be to start at the beginning, examine each entry one at a time, and continue until you find the name. No one uses that method: instead, you open the book to some interior page and look for the name on that page. If it is there, you are done; otherwise, you eliminate either the part of the book before the current page or the part of the book after the current page from consideration and repeat.
Exception filter. We now use binary search to solve the existence problem: is a given key in a sorted database of keys? For example, when checking the spelling of a word, you need only know whether your word is in the dictionary and are not interested in the definition. In a computer search, we keep the information in an array, sorted in order of the key. The binary search code in BinarySearch.java differs from our other applications in two details. First, the file size N need not be a power of two. Second, it has to allow the possibility that the item sought is not in the array. The client program implements an exception filter: it reads a sorted list of strings from a file (which we refer to as the whitelist) and an arbitrary sequence of strings from standard input and prints those in the sequence that are not in the whitelist.

Insertion sort.

Insertion sort is a brute-force sorting algorithm that is based on a simple method that people often use to arrange hands of playing cards. Consider the cards one at a time and insert each into its proper place among those already considered (keeping them sorted). The following code mimics this process in a Java method that sorts strings in an array:

public static void sort(double[] a) {
   int N = a.length;
   for (int i = 0; i < N; i++)
      for (int j = i; j > 0; j--)
         if (a[j-1].compareTo(a[j]) > 0)
             exch(a, j, j-1);
         else break;
}

The outer for loop sorts the first i entries in the array; the inner for loop can complete the sort by putting a[i] into its proper position in the array.

Mathematical analysis. The inner loop of the insertion sort code is within a double for loop, which suggests that the running time is quadratic, but we cannot immediately draw this conclusion because of the break.
- Best case. When the input array is already in sorted order, the inner for loop amounts to nothing more than a comparison (to learn that a[j-1] is less than a[j]) and the break, so the total running time is linear.
- Worst case. When the input is reverse sorted, the inner loop fully completes without a break, so the frequency of execution of the instructions in the inner loop is 1 + 2 + ... + N-1 ~ N^2 and the running time is quadratic.
- Average case. When the input is randomly ordered To understand the performance of insertion sort for randomly ordered, we expect that each new element to be inserted is equally likely to fall into any position, so that element will move halfway to the left on average. Thus, we expect the running time to be 1/2 + 2/2 + ... + (N-1)/2 ~ N^2 / 2.
Sorting other types of data. We want to be able to sort all types of data, not just strings. For sorting objects in an array, we need only assume that we can compare two elements to see whether the first is bigger than, smaller than, or equal to the second. Java provides the Comparable interface for precisely this purpose. Simply put, a class that implements the Comparable interface promises to implement a method compareTo() for objects of its type so that that a.compareTo(b) returns a negative integer if a is less than b, a positive integer if a is greater than b, and 0 if a is equal to b. The precise meanings of less than, greater than, and equal to are up to the data type, though implementations that do not respect the natural laws of mathematics surrounding these concepts will yield unpredictable results. With this convention, Insertion.java implements insertion sort so that it sorts arrays of Comparable objects.
Empirical analysis. Program InsertionTest.java tests our hypothesis that insertion sort is quadratic for randomly ordered files. It relies on the helper data type Stopwatch.java.
Sensitivity to input. Note that InsertionTest.java takes a command-line parameter M and runs M experiments for each array size, not just one. One reason for doing so is that the running time of insertion sort is sensitive to its input values. It is not correct to flatly predict that the running time of insertion sort will be quadratic, because your application might involve input for which the running time is linear.

Mergesort.

To develop a faster sorting method, we use a divide-and-conquer approach to algorithm design that every programmer needs to understand. This nomenclature refers to the idea that one way to solve a problem is to divide it into independent parts, conquer them independently, and then use the solutions for the parts to develop a solution for the full problem. To sort an array with this strategy, we divide it into two halves, sort the two halves independently, and then merge the results to sort the full array. This method is known as mergesort. To sort a[lo, hi), we use the following recursive strategy:

base case: If the subarray size is 0 or 1, it is already sorted.
recursive step: Otherwise, compute m = lo + (hi - lo)/2, sort (recursively) the two subarrays a[lo, m) and a[m, hi), and merge them to produce a sorted result.

Merge.java is an implementation. As usual, the easiest way to understand the merge process is to study a trace of the contents of the array during the merge.

Mathematical analysis. The inner loop of mergesort is centered on the auxiliary array. The two for loops involve N iterations (and creating the array takes time proportional to N), so the frequency of execution of the instructions in the inner loop is proportional to the sum of the subarray sizes for all calls to the recursive function. The value of this quantity emerges when we arrange the calls on levels according to their size. On the first level, we have 1 call for size N, on the second level, we have 2 calls for size N/2, on the third level, we have 4 calls for size N/4, and so forth, down to the last level with N/2 calls of size 2. There are precisely lg N levels, giving the grand total N lg N for the frequency of execution of the instructions in the inner loop of mergesort. This equation justifies a hypothesis that the running time of mergesort is linearithmic.
Quadratic-linearithmic chasm. The difference between N^2 and N lg N makes a huge difference in practical applications. Understanding the enormousness of this difference is another critical step to understanding the importance of the design and analysis of algorithms. For a great many important computational problems, a speedup from quadratic to linearithmic makes the difference between being able to solve a problem involving a huge amount of data and not being able to effectively address it at all.
Divide-and-conquer algorithms. The same basic approach is effective for many important problems, as you will learn if you take a course on algorithm design.
Reduction to sorting. A problem A reduces to a problem B if we can use a solution to B to solve A. Designing a new divide-and-conquer algorithm from scratch is sometimes akin to solving a puzzle that requires some experience and ingenuity, so you may not feel confident that you can do so at first. But it is often the case that a simpler approach is effective: given a new problem that lends itself to a quadratic brute-force solution, ask yourself how you would solve it if the data were sorted in some way. For example, consider the problem of determining whether the elements in an array are all different. This problem reduces to sorting because we can sort the array, the make a linear pass through the sorted array to check whether any entry is equal to the next (if not, the elements are all different.)

Frequency counts.

FrequencyCount.java reads a sequence of strings from standard input and then prints a table of the distinct values found and the number of times each was found, in decreasing order of the frequencies. We accomplish this by two sorts.

Computing the frequencies. Our first step is to sort the strings on standard input. In this case, we are not so much interested in the fact that the strings are put into sorted order, but in the fact that sorting brings equal strings together. If the input is
to be or not to be to
then the result of the sort is
be be not or to to to
with equal strings like the three occurrences of to brought together in the array. Now, with equal strings all together in the array, we can make a single pass through the array to compute all the frequencies. The Counter.java data type that we considered in Section 3.x is the perfect tool for the job.
Sorting the frequencies. Next, we sort the Counter objects. We can do so in client code without any special arrangements because Counter implements the Comparable interface.
Zipf's law. The application highlighted in FrequencyCount is elementary linguistic analysis: which words appear most frequently in a text? A phenomenon known as Zipf's law says that the frequency of the ith most frequent word in a text of M distinct words is proportional to 1/i.

Longest repeated substring.

Another important computational task that reduces to sorting is the problem of finding the longest repeated substring in a given string. This problem is simple to state and has many important applications, including computer-assisted music analysis, cryptography, and data compression. Think briefly about how you might solve it. Could you find the longest repeated substring in a string that has millions of characters? Program LRS.java is a clever solution that uses suffix sorting.

Quicksort.

Quicksort is a divide-and-conquer method for sorting. It works by partitioning an array of elements into two parts, then sorting the parts independently. As we shall see, the precise position of the partition depends on the initial order of the elements in the input file. The crux of the method is the partitioning process, which rearranges the array to make the following three conditions hold:

The element a[i] is in its final place in the array for i.
None of the elements a[left], ..., a[i-1] is greater than a[i].
None of the elements in a[i+1], ..., a[right] is less than a[i].

We achieve a complete sort by partitioning, then recursively applying the method to the subfiles.

We use the following general strategy to implement partitioning. First, we arbitrarily choose a[right] to be the partitioning element - the one that will go into its final position. Next, we scan from the left end of the array until we find an element greater than the partitioning element, and we scan from the right end of the array until we find an element less than the partitioning element. The two elements that stopped the scans are obviously out of place in the final partitioned array, so we exchange them. Continuing in this way, we ensure that no array elements to the left of the left index are greater than the partitioning element, and no array elements to the right of the right index are less than the partitioning element, as depicted in the following diagram.

When the scan indices cross, all that we need to do to complete the partitioning process is to exchange a[right] with the leftmost element of the right subfile (the element pointed to by the left index i).

Program QuickSort.java implements this algorithm.

Q + A

Q. Why do we need to go to such lengths to prove a program correct?

A. To spare ourselves considerable pain. Binary search is a notable example. For example, you now understand binary search; a classic programming exercise is to write a version that uses a while loop instead of recursion. Try solving Exercise 4.2.2 without looking back at the code in the book. In a famous experiment, J. Bentley once asked several professional programmers to do so, and most of their solutions were not correct. According to Knuth, the first binary search algorithm was published in 1946, but the first published binary search without bugs did not appear until 1962.

Q. Are there implementations for sorting and searching in the Java libarary?

A. Yes. The Java library java.util.Arrays contains the methods Arrays.sort() and Arrays.binarySearch() that implement mergesort and binary search for Comparable types and a sorting implementation for primitive types based on a version of the quicksort algorithm, which is faster than mergesort and also sorts an array in place (without using any extra space). SystemSort.java illustrates how to use Arrays.sort().

Q. So why not just use them?

A. Feel free to do so. As with many topics we have studied, you will be able to use such tools more effectively if you understand the background behind them.

Q. Why doesn't the Java library use a randomized version of quicksort?

A. Good question. At the very least, the library should cutoff to some guaranteed N log N algorithm if it "realizes" it is in trouble. Perhaps to avoid side effects. Programmers may want their libraries to be deterministic for debugging. But the library only uses quicksort for primitive types when stability is not an issue, so the programmer probably wouldn't notice the randomness, except in running time.

Exercises

Develop an implementation of TwentyQuestions.java that takes the maximum number N as command-line input. Prove that your implementation is correct and that using Program 4.2.1 for the smallest power of two not smaller than N uses at most one more question.
Add code to Insertion to produce the trace given in the text.
Add code to Merge to produce the trace given in the text.
Show that binary search in a sorted array is logarithmic as long as it eliminates at least a constant fraction of the array at each step.
Analyze mergesort mathematically, as we did for binary search.
Analyze mergesort for the case when N not a power of two.
Give traces of insertion sort and mergesort, in the style, of the traces in the text, for the input
it was the best of times it was.
Write a program Dedup.java that reads a sequence of strings from standard input and prints them on standard output with all duplicates removed.
Write a version of compareTo() for comparing two strings that uses lcp(), then checks lengths and compares two characters to finish the job.
Add code to LRS.java to make it print indices in the original string where the repeated substrings occur.
Write a program that finds the longest common substring of two given strings s and t.
Hint: concatenate a unique character to the end of each string, say '\1' and '\2'. Form all suffixes of s and t, suffix sort all of them together, and identify the longest prefix in two adjacent suffixes, subject to the condition that one suffix comes from s and one from t. You can tell which string a suffix corresponds by looking at its last character.
Hint: Or suffix sort each string. Then merge the two sorted suffixes together, keeping track of the consecutive strings that arose from different input strings.
Modify LRS.java to find the longest repeated substring that does not overlap.
Write a program to read in a list of domain names from standard input, and print the reverse domains in sorted order. For example, the reverse domain of cs.princeton.edu is edu.princeton.cs. This computation is useful for web log analysis.

Algorithm Design Exercises

This list of exercises is intended to give you experience in developing fast solutions to typical problems. Think about using binary search, mergesort, or devising your own divide-and-conquer algorithm. Implement and test your algorithm.

Add to StdStats a method that computes in linearithmic time the median of a sequence of N integers. Hint : Reduce to sorting.
Add to StdStats a method that computes in linear time the mode (value that occurs most frequently) of a sequence of N integers.
Answer: sort the integers, then count up the number of occurrences of each, and return an integer with the maximum number of occurrences.
Write a program to sort in linear time a sequence of N integers that are between 0 and 99.
Hint: populate an array freq[] so that freq[i] stores the number of occurrences of the integer i.
Given an array of N real numbers, write a static method to find in linearithmic time the pair of integers that are closest in value.
Hint: sorting brings the closest pair together.
Given an array of N real numbers, write a static method to find in linear time the pair of integers that are farthest apart in value.
Hint: find the maximum and minimum integers.
Write a static method that takes as argument three arrays of strings, determines whether there is any string common to all three arrays, and if so, returns the first such name, in running time linearithmic in the total number of strings.
Hint: sort each of the three lists, then describe how to do a "3-way" merge.
Write a static method that takes a sorted list of integers and a target integer x and determines in linear time whether there are any two that sum to exactly x.
An element is a majority if it appears more than N/2 times. Write a static method that takes an array of N strings as argument and identifies a majority (if it exists) in linear time.

Web Exercises

Write a non-recurisve version of BinarySearch.search().

public static int binarySearch(long[] a, long key) {
   int bot = 0;
   int top = a.length - 1;
   while (bot <= top) {
      int mid = bot + (top - bot) / 2;
      if      (key < a[mid]) top = mid - 1;
      else if (key > a[mid]) bot = mid + 1;
      else return mid;
   }
   return -1;
}

Describe what happens when you binary search in an unsorted array. Would it be wise to check whether the array is sorted before each call to binary search? Could you check that the elements binary search touches are in ascending order?
Given a sorted list of N integers and a target integer x, determine in O(N) time whether there are any two that sum to exactly x.
Hint: maintain an index lo = 0 and hi = N-1 and compute a[lo] + a[hi]. If the sum equals x, you are done; if the sum is less than x, decrement hi; if the sum is greater than x, increment lo. Be careful if one (or more) of the integers are 0.
Let f be a monotonically increasing function with f(0) < 0 and f(N) > 0. Find the smallest integer i such that f(i) > 0. Devise an algorithm that makes O(log N) calls to f().
Hint: assuming we know N, maintaing an interval [lo, hi] such that f[lo] < 0 and f[hi] > 0 and apply binary search. If we don't know N, repeatedly compute f(1), f(2), f(4), f(8), f(16), and so on until you find a value of N such that f(N) > 0.
Let a[] be an array that starts out increasing, reaches a maximum, and then decreases. Design an O(log N) algorithm to find the index of the maximum value.
Hint: divide the interval into three equal size pieces and devise a way to safely throw away one of the thirds.
Give an O(N log N) algorithm for computing the median of a sequence of N integers.
Answer: sort and return element N/2.
Given two sorted lists of size N₁ and N₂, find the median of all elements in O(log N) time where N = N₁ + N₂.
Hint: design a more general algorithm that finds the kth largest element for any k. Compute the median element in the large of the two lists and; throw away at least 1/4 of the elements and recur.
Given an array of N integers, the 2-sum problem is to find a pair of integers whose sum is closest to zero. Describe an O(N log N) algorithm for the problem.
Solution. Sort by absolute value - the best pair is now adjacent.
Give an array of N long integers, devise an O(N log N) algorithm to determine if any two are equal.
Hint: sorting brings equal values together.
Give a sorted array of N elements, possibly with duplicates, find the index of the first and last occurrence of k in O(log N) time.
Hint: modify binary search.
Give a sorted array of N elements, possibly with duplicates, find the number of occurrences of element k in O(log N) time.
Hint: see the previous exercise.
Given an array of N integers, the 3-sum problem is to determine find three integers whose sum is closest to zero. Design an algorithm that uses O(N² log N) time and O(N) space. Hint: sort and binary search.
Design an algorithm for the 3-sum problem that runs in O(N²) time and O(N) space. Hint: sort and clever search.

Creative Exercises

Floor and ceiling. Given a set of comparable elements, the ceiling of x is the smallest element in the set greater than or equal to x, and the floor is the largest element less than or equal to x. Suppose you have an array of N elements in ascending order. Give an O(log N) algorithm to find the floor and ceiling of x.
Union of intervals. Given N intervals on the real line, determine the length of their union in O(N log N) time. For example the union of the four intervals [1, 3], [2, 4.5], [6, 9], and [7, 8] is 6.5.
Coffee can problem. (David Gries). Suppose you have a coffee can which contains an unknown number of black beans and an unknown number of white beans. Repeat the following process until exactly one bean remains: Select two beans from the can at random. If they are both the same color, throw them both out, but insert another black bean. If they are different colors, throw the black one away, but return the white one. Prove that this process terminates with exactly one bean left. What can you deduce about the color of the last bean as a function of the initial number of black and white beans? Hint: find a useful invariant maintained by the process.
Spam campaign. To initiate an illegal spam campaign, you have a list of email addresses from various domains (the part of the email address that follows the @ symbol). To better forge the return addresses, you want to send the email from another user at the same domain. For example, you might want to forge an email from nobody@princeton.edu to somebody@princeton.edu. How would you process the email list to make this an efficient task?
Order statistics. Given an array of N elements, not necessarily in ascending order, devised an algorithm to find the kth largest one. It should run in O(N) time on random inputs.
Kendall's tau distance. Given two permutations, Kendall's tau distance is the number of pairs out of position. "Bubblesort metric." Give an O(N log N) algorithm to compute the Kendall tau distance between two permutations of size N. Useful in top-k lists, social choice and voting theory, comparing genes using expression profiles, and ranking search engine results.
Antipodal points. Given N points on a circle, centered at the origin, design an algorithm that determines whether there are two points that are antipodal, i.e., the line connecting the two points goes through the origin. Your algorithm should run in time proportional to N log N.
Antipodal points. Repeat the previous question, but assume the points are given in clockwise order. Your algorithm should run in time proportional to N.
Identity. Given an array a of N distinct integers (positive or negative) in ascending order. Devise an algorithm to find an index i such that a[i] = i if such an index exists. Hint: binary search.
L1 norm. There are N circuit elements in the plane. You need to run a special wire (parallel to the x-axis) across the circuit. Each circuit element must be connected to the special wire. Where should you put the special wire? Hint: median minimizes L1 norm.
Finding common elements. Given two arrays of N 64-bit integers, design an algorithm to print out all elements that appear in both lists. The output should be in sorted order. Your algorithm should run in N log N. Hint: mergesort, mergesort, merge. Remark: not possible to do better than N log N in comparison based model.
Finding common elements. Repeat the above exercise but assume the first array has M integers and the second has N integers where M is much less than N. Give an algorithm that runs in N log M time. Hint: sort and binary search.
Prefix free codes. In data compression, a set of binary code words is prefix-free if no string is a prefix of another. For example, { 01, 10, 0010, 1111 } is prefix free, but { 01, 10, 0010, 1010 } is not because 10 is a prefix of 1010. Design an efficient algorithm to determine if a set of binary code words is prefix-free. Hint: sort.
Sampling from a discrete probability distribution. Binary search of cumulative sums.
Anagrams. Design a O(N log N) algorithm to read in a list of words and print out all anagrams. For example, the strings "comedian" and "demoniac" are anagrams of each other. Assume there are N words and each word contains at most 20 letters. Designing a O(N^2) algorithms should not be too difficult, but getting it down to O(N log N) requires some cleverness.
Pattern recognition. Given a list of N points in the plane, find all subset of 3 or more points that are collinear.
Pattern recognition. Given a list of N points in the plane in general position (no three are collinear), find a new point p that is not collinear with any pair of the N original points.
Search in a sorted, rotated list. Given a sorted list of N integers that has been rotated an unknown number of positions, e.g., 15 36 1 7 12 13 14, design an O(log N) algorithm to determine if a given integer is in the list.
Counting inversions. Each user ranks N songs in order of preference. Given a preference list, find the user with the closest preferences. Measure "closest" according to the number of inversions. Devise an N log N algorithm for the problem.
Throwing cats from an N-story building. Suppose that you have an N story building and a bunch of cats. Suppose also that a cat dies if it is thrown off floor F or higher, and lives otherwise. Devise a strategy to determine the floor F, while killing O(log N) cats.
Throwing cats from a building. Repeat the previous exercise, but devise a strategy that kills O(log F) cats. Hint: repeated doubling and binary search.
Throwing two cats from an N-story building. Repeat the previous question, but now assume you only have two cats. Now your goal is to minimize the number of throws. Devise a strategy to determine F that involves throwing cats O(√N) times (before killing them both). This application might occur in practice if search hits (cat surviving fall) are much cheaper than misses (cat dying).
Throwing two cats from a building. Repeat the previous question, but only throw O(√F) cats. Reference: ???.
Nearly sorted. Given an array of N elements, each which is at most k positions from its target position, devise an algorithm that sorts in O(N log k) time.
Solution 1: divide the file into N/k pieces of size k, and sort each piece in O(k log k) time, say using mergesort. Note that this preserves the property that no element is more than k elements out of position. Now, merge each blocks of k elements with the block to its left.
Solution 2: insert the first k elements into a binary heap. Insert the next element from the array into the heap, and delete the minimum element from the heap. Repeat.
Merging k sorted lists. Suppose you have k sorted lists with a total of N elements. Give an O(N log k) algorithm to produce a sorted list of all N elements.
Dutch national flag problem. Given an array a[] of elements and a partitioning element p, rearrange it into three pieces: those with keys less than a[p], those with keys equal to a[p], and those with keys greater than a[p]. Do it in-place, i.e., with at most a constant amount of extra memory. Application: 3-way quicksort. Prove that your algorithm is correct in all cases by identifying loop invariants.
Longest common reverse complemented substring. Given two DNA strings, find the longest substring that appears in one, and whose reverse Watson-Crick complement appears in the other. Two strings s and t are reverse complements if t is the reverse of s except with the following substitutions A<->T, C<->G. For example ATTTCGG and CCGAAAT are reverse complements of each other. Hint: suffix sort.
Circular string linearization. Plasmids contain DNA in a circular molecule instead of a linear one. To facilitate search in a database of DNA strings, we need a place to break it up to form a linear string. A natural choice is the place that leaves the lexicographically smallest string. Devise an algorithm to compute this canonical representation of the circular string Hint: suffix sort.
Find all matches. Given a text string, find all matches of the query string. Hint: combine suffix sorting and binary search.
Longest repeated substring with less memory. Instead of using an array of substrings where suffixes[i] refers to the ith sorted suffix, maintain an array of integers so that index[i] refers to the offset of the ith sorted suffix. To compare the substrings represented by a = index[i] and b = index[j], compare the character s.charAt(a) against s.charAt(b), s.charAt(a+1) against s.charAt(b+1), and so forth. How much memory do you save? Is your program faster?
Idle time. Suppose that a parallel machine processes n jobs. Job j is processed from s_j to t_j. Given the list of start and finish times, find the largest interval where the machine is idle. Find the largest interval where the machine is non-idle.
Local minimum of an array. Given an array a of N distinct integers, design an O(log N) algorithm to find a local minimum: an index i such that a[i-1] < a[i] < a[i+1].
Solution. Query middle value a[n/2], and two neighbors a[n/2 - 1] and a[n/2 + 1]. If a[n/2] is local minimum, stop; otherwise search in half with smaller neighbor.
Local minimum of a matrix. Given an N-by-N array a of N² distinct integers, design an O(N) algorithm to find a local minimum: an pair of indices i and j such that a[i][j] < a[i+1][j], a[i][j] < a[i][j+1], a[i][j] < a[i-1][j], and a[i][j] < a[i][j-1].
Bitonic search. An array is bitonic if it is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Given a bitonic array a of N distinct integers, describe how to determine whether a given integer is in the array in O(log N) steps. Hint: find the local maximum, then binary search in each piece.
Monotone 2d array. Give an n-by-n array of elements such that each row is in ascending order and each column is in ascending order, devise an O(n) algorithm to determine if a given element x in the array. You may assume all elements in the n-by-n array are distinct.
Maxima. Given a set of n points in the plane, point (xi, yi) dominates (xj, yj) if xi > xj and yi > yj. A maxima is a point that is not dominated by any other point in the set. Devise an O(n log n) algorithm to find all maxima. Application: on x-axis is space efficiency, on y-axis is time efficiency. Maxima are useful algorithms. Hint: sort in ascending order according to x-coordinate; scan from right to left, recording the highest y-value seen so far, and mark these as maxima.
Compound words. Read in a list of words from standard input, and print out all two-word compound words. If after, thought, and afterthought are in the list, then afterthought is a compound word. Note: the components in the compound word need not have the same length.
Smith's rule. The following problem arises in supply chain management. You have a bunch of jobs to schedule on a single machine. (Give example.) Job j requires p[j] units of processing time. Job j has a positive weight w[j] which represents its relative importance - think of it as the inventory cost of storing the raw materials for job j for 1 unit of time. If job j finishes being processed at time t, then it costs t * w[j] dollars. The goal is to sequence the jobs so as to minimize the sum of the weighted completion times of each job. Write a program SmithsRule.java that reads in a command line parameter N and a list of N jobs specified by their processing time p[j] and their weight w[j], and output an optimal sequence in which to process their jobs. Hint: Use Smith's rule: schedule the jobs in order of their ratio of processing time to weight. This greedy rule turns out to be optimal.
Sum of four primes. The Goldbach conjecture says that all positive even integers greater than 2 can be expressed as the sum of two primes. Given an input parameter N (odd or even), express N as the sum of four primes (not necessarily distinct) or report that it is impossible to do so. To make your algorithm fast for large N, do the following steps:
1. Compute all primes less than N using the Sieve of Eratosthenes.
2. Tabulate a list of sums of two primes.
3. Sort the list.
4. Check if there are two numbers in the list that sum to N. If so, print out the corresponding four primes.
Typing monkeys and power laws. (Micahel Mitzenmacher) Suppose that a typing monkey creates random words by appending each of 26 possible lettter with probability p to the current word, and finishes the word with probability 1 - 26p. Write a program to estimate the frequency spectrum of the words produced.

Typing monkeys and power laws. Repeat the previous exercise, but assume that the letters a-z occur proportional to the following probabilities, which are typical of English text.

CHAR	FREQ	CHAR	FREQ	CHAR	FREQ	CHAR	FREQ	CHAR	FREQ
A	8.04	G	1.96	L	4.14	Q	0.11	V	0.99
B	1.54	H	5.49	M	2.53	R	6.12	W	1.92
C	3.06	I	7.26	N	7.09	S	6.54	X	0.19
D	3.99	J	0.16	O	7.60	T	9.25	Y	1.73
E	12.51	K	0.67	P	2.00	U	2.71	Z	0.09
F	2.30

Binary search. Justify why the following modified version of binarySearch() works. Prove that if the key is in the array, it correctly returns the smallest index i such that a[i] = key; if the key is not in the array, it returns -i where i is the smallest index such that a[i] > key.

// precondition array a in ascending order
public static int binarySearch(long[] a, long key) {
   int bot = -1;
   int top = a.length;
   while (top - bot > 1) {
      int mid = bot + (top - bot) / 2;
      if (key > a[mid]) bot = mid;
      else              top = mid;
   }
   if (a[top] == key) return  top;
   else               return -top - 1;
}

Answer. The while loop invariant says top >= bot + 2. This implies bot < mid < top. Hence length of interval strictly decreases in each iteration. While loop also maintains the invariant: a[bot] < key <= a[top], with the contention that a[-1] is -infinity and a[N] is +infinity.

Binary search bugs. Joshua Bloch reports Bentley's implementation contains a subtle bug. Same bug appears in Sun's Java 1.5 implementation. The following line fails if lo + hi overflows a 32-bit int. This can happen if the array contains around a billion elements.
int mid = (lo + hi) / 2;
Here are two corrected versions.
int mid = lo + (hi - lo) / 2; int mid = (lo + hi) >>> 1;
Range search. Given a database of all tolls collected in NJ road system in 2006, devise a scheme to answer queries of the form: extract sum of all tolls collected in a given time interval. Use a Toll data type that implements the Comparable interface, where the key is the time that the toll was collected.
Hint: sort by time, compute a cumulative sum of the first i tolls, then use binary search to find the desired interval.
Rhyming words. For your poetry class, you would like to tabulate a list of rhyming words. A crude way to accomplish this task is as follows:
- Read in a dictionary of words into an array of strings.
- Reverse the letters in each word, e.g., confound becomes dnuofnoc.
- Sort the resulting array of words.
- Reverse the letters in each word back to their original state.
Now the word confound will be next to words like astound and compound. Write a program Rhymer.java that reads in a sequence of words from standard input and prints them out in the order specified above.
Longest repeated substrings. Modify LRS.java to find all longest repeated substrings.

Scientific example of sorting. Google display search results in descending order of "importance", a spreadsheet displays columns sorted by a particular field, Matlab sorts the real eigenvalues of a symmetric matrix in descending order. Sorting also arises as a critical subroutine in many applications that appear to have nothing to do with sorting at all including: data compression (see the Burrows-Wheeler programming assignment), computer graphics (convex hull, closest pair), computational biology (longest common substring discussed below), supply chain management (schedule jobs to minimize weighted sum of completion times), combinatorial optimization (Kruskal's algorithm), social choice and voting (Kendall's tau distance), Historically, sorting was most important for commercial applications, but sorting also plays a major role in the scientific computing infrastructure. NASA and the fluids mechanics community use sorting to study problems in rarefied flow; these collision detection problems are especially challenging since they involve ten of billions of particles and can only be solved on supercomputers in parallel. Similar sorting techniques are used in some fast N-body simulation codes. Another important scientific application of sorting is for load balancing the processors of a parallel supercomputers. Scientists rely on clever sorting algorithm to perform load-balancing on such systems.