Programming Praxis

We saw in the previous exercise that finding an exact solution for the traveling salesman problem is extremely time consuming, taking time O(n!). The alternative is a heuristic that delivers a reasonably good solution quickly. One such heuristic is the “nearest neighbor:” pick a starting point, then at each step pick the nearest unvisited point, add it to the current tour and mark it visited, repeating until there are no unvisited points.

Your task is to write a program that solves the traveling salesman problem using the nearest neighbor heuristic. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

The traveling salesman problem is classic: Find the minimum-length tour that visits each city on a map exactly once, returning to the origin. It is an important problem in practice; consider, for instance, that the cities are soldering points on a large circuit board, each of which must be visited by a soldering robot. It is also an important problem in mathematics, and is known to be in NP, meaning that optimal solutions for non-trivial problems are impossible. Nonetheless, there exist heuristic algorithms that do a good job at minimizing the tour length.

We will examine the traveling salesman problem in an occasional series of exercise, beginning with today’s exercise that looks at the brute-force solution of examining all possible tours. The algorithm is simple: First, select a tour at random, then determine all possible permutations of the tour. Second, determine the length of each tour. Third, report the tour with minimum length as the solution.

Your task is to write a program that solves the traveling salesman problem using the brute-force algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Edsger Dijkstra, in his book A Discipline of Programming, describes a function that, given a list of elements and a function that returns a total ordering of those elements, produces the next lexicographic permutation of the list; for instance, the permutations of the list (1 2 3 4) in lexicographic order are (1 2 3 4) (2 1 3 4) (1 3 2 4) (3 1 2 4) (2 3 1 4) (3 2 1 4) (1 2 4 3) (2 1 4 3) (1 4 2 3) (4 1 2 3) (2 4 1 3) (4 2 1 3) (1 3 4 2) (3 1 4 2) (1 4 3 2) (4 1 3 2) (3 4 1 2) (4 3 1 2) (2 3 4 1) (3 2 4 1) (2 4 3 1) (4 2 3 1) (3 4 2 1) (4 3 2 1). With the least significant item in the list at the head, the next greater element than (1 2 3 4) is (2 1 3 4), since the most significant tail of the list doesn’t change, and the next greater permutation differs in the least significant elements. To make a greater permutation, some element of the list must be replaced by a larger element to its left; to make the next permutation, the replacement must happen as far to the left as possible, in the least significant position, and the replacing element must be as small as possible.

Your task is to write functions that return the next lexicographic permutation and a list of all permutations of a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Binary search trees are a simple and commonly-used data structure. A binary search tree is a hierarchical data structure in which each node stores a key, a value, and pointers to two children. Each node has one parent, except the node at the root of the tree, which has no parents. At each node, the key is greater than or equal to the keys of all nodes in its left child and less than or equal to the keys of all nodes in its right child. Any node may be null; a null node has no key, no value, and no children. A sample binary search tree is shown at the right.

Traversing the tree is fairly simple. Start at the root, comparing the key at the current node to the key being sought. If the target key is less than the current key, repeat the search at the left child; likewise, if the target key is greater than the current key, repeat the search at the right child. If the target key and current key are the same, you’ve found the desired node; if you reach a null node, the target key is not present in the tree. The insert and delete operations maintain the in-order property at each node.

Your task is to write functions that manipulate binary search trees; you should include lookup, insert, delete, and enlist functions in your library. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Christian Goldbach (1690-1764) was a Prussian mathematician and contemporary of Euler. One of the most famous unproven conjectures in number theory is known as Goldbach’s Conjecture, which states that every even number greater than two is the sum of two prime numbers; for example, 28 = 5 + 23.

Your task is to write a function that finds the two primes that add to a given even number greater than two. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A book by Brian Kernighan and P. J. Plauger, Software Tools in Pascal, describes a pair of programs, called compress and expand, that provide run-length encoding of text files. The compress program takes a text file as input and writes a (hopefully smaller) version of the text file as output; the expand program inverts that operation. Compression is achieved by replacing runs of four or more of the same character with a three-character code consisting of a tilde, a letter A through Z indicating 1 through 26 repetitions, and the character to be repeated. Runs longer than 26 characters are replaced by multiple encodings, andany literal appearance of the tilde in the input is encoded as a run of length 1. For instance, the string ABBB~CDDDDDEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE is encoded as ABBB~A~C~ED~ZE~DE.

Your task is to write programs that compress and expand a text file. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

We examined quicksort in a previous exercise. Today we examine a version of quicksort that Jon Bentley spoke about at Google, reprising the quicksort function that he and Doug McIlroy explained in their article “Engineering a Sort Function” in Software—Practice and Experience (Volume 23, Number 11, Pages 1249–1265, November 1993).

The Bentley/McIlroy quicksort is characterized by an adaptive pivot selection, a fast approaching-pointers partition, use of ternary comparison operator (less-than, equal-to, greater-than) to enable a “fat pivot,” and insertion sort for small sub-arrays. The quicksort also uses a fast swap that adapts to the size of the data elements. The adaptive pivot selection uses the middle element for small arrays, the median of the first, middle and last elements for medium-sized arrays, and the median of nine equally-spaced elements for larger arrays. This description doesn’t really do justice to the code; you should read the article for details.

Your task is to write a quicksort function using the same algorithm as Bentley and McIlroy. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

We examined the Sieve of Atkin for enumerating prime numbers in a recent exercise. Though the Sieve of Atkin has the potential to be faster than the Sieve of Eratosthenes, our implementation was not; the Sieve of Eratosthenes takes 1.219 seconds to enumerate the first million primes, our implementation of the Sieve of Atkins takes 22.954 seconds, nineteen times as long, to perform the same task.

The problem is that the naive implementation we used performs useless work. For instance, consider that you are sieving the numbers to a million, with the x and y variables of the naive implementation ranging from one to a thousand. In the first case, with 4x² + y² = k, 4·1000² + 1000² = 5000000, which is far beyond the end of the range being sieved. Reducing the limits means a lot less work and a much faster program.

Your task is to rewrite the naive Sieve of Atkins to eliminate useless work. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Soundex is an algorithm originally developed by Margaret Odell and Robert Russell in the early 1900s to convert people’s last names into a standard encoding in a way that brings together similar names, thus correcting misspellings. Knuth (AoCP3, introduction to Chapter 6) describes the algorithm as follows:

1. Retain the first letter of the name, and drop all occurrences of a, e, h, i, o, u, w, y in other positions.
2. Assign the following numbers to the remaining letters after the first:
   • b, f, p, v → 1
   • c, g, j, k, q, s, x, z → 2
   • d, t → 3
   • l → 4
   • m, n → 5
   • r → 6
3. If two or more letters with the same code were adjacent in the original name (before step 1), omit all but the first.
4. Convert to the form “letter, digit, digit, digit” by adding trailing zeros (if there are less than three digits), or by dropping rightmost digits (if there are more than three).

The soundex method isn’t perfect. As Knuth points out, related names like Rogers and Rodgers, or Sinclair and St. Clair, or Tchebysheff and Chebyshev, are not matched. On the other hand, soundex works well enough to be generally useful, and if your first attempt at a match fails, it isn’t too hard to try again with an alternate spelling.

Your task is to write a function that takes a name and returns its associated soundex code. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

We examined the use of the Sieve of Eratosthenes for enumerating the prime numbers, a method that dates to the ancient Greeks, in two previous exercises. Just a few years ago, in 2004, A. O. L. Atkin and D. J. Bernstein developed a new method, called the Sieve of Atkin, that performs the same task more quickly. The new method first marks squarefree potential primes, then eliminates those potential primes that are not squarefree.

Atkin’s sieve begins with a boolean array (bits are fine) of length n equal to the number of items to be sieved; each element of the array is initially false.

Squarefree potential primes are marked like this: For each element k of the array for which k ≡ 1 (mod 12) or k ≡ 5 (mod 12) and there exists some 4x² + y² = k for positive integers x and y, flip the sieve element (set true elements to false, and false elements to true). For each element k of the array for which k ≡ 7 (mod 12) and there exists some 3x² + y² = k for positive integers x and y, flip the sieve element. For each element k of the array for which k ≡ 11 (mod 12) and there exists some 3x² – y² = k for positive integers x and y with x > y, flip the sieve element.

Once this preprocessing is complete, the actual sieving is performed by running through the sieve starting at 7. For each true element of the array, mark all multiples of the square of the element as false (regardless of their current setting). The remaining true elements are prime.

Your task is to write a function to sieve primes using the Sieve of Atkin. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.