Programming Praxis

It was a dreary Sunday in St Louis, unseasonably warm, but it rained all day and felt much colder than the actual air temperature, so I sat down to read Donald Knuth’s article, with Svante Janson, Shellsort With Three Increments. After sixteen pages, Janson and Knuth conjecture but do not prove that the gap sequence (h, g, 1) with h ≈ √n and g ≈ √h and h coprime to g leads to time complexity O(n^3/2).

Your task is to implement shellsort, as we did in a previous exercise, and test the Janson/Knuth conjecture. 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.

Pages: 1 2

Some numbers can be represented as the sum of a sequence of consecutive squares; for instance, 595 = 6² + 7² + 8² + 9² + 10² + 11² + 12². Other numbers are not so representable.

Your task is to write a program that finds the longest consecutive sequence of squares that sums to a given number, or determines that no such sequence exists. 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.

Pages: 1 2

We discussed an algorithm due to Lenore Blum, Manuel Blum and Michael Shub that generates cryptographically-secure random numbers in a previous exercise. A better way to generate these random numbers uses an actual hardware source of entropy, such as thermal noise.

I recently learned that all models of the Raspberry Pi computer include a hardware random number generator on their system-on-a-chip; Stewart Russell gives instructions.

If instead of a Raspberry Pi you have a computer based on the Intel Ivy Bridge family of processors, a hardware random number generator is available as rdrand; Linux exposes that as the /dev/random device.

Your task is to explore the hardware random number generators that are available to you; you might want to write a program to generate keypads for the Diana Cryptosystem. 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.

Pages: 1 2

Today’s task is a simple exercise in list handling:

Given a list of integers, find the place where the list can be split in two that minimizes the differences in the sums of the two halves of the list. For instance, given the list [3,7,4,2,1], splitting after the second element of the list gives sums of 10 and 7 for the two halves of the list, for a difference of 3, and no other split gives a lower difference.

Your task is to write a program that splits a list as indicated above. 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.

Pages: 1 2

I had too much Thanksgiving; more specifically, the stuffing went bad, and I’ve felt poorly the last few days. In between trips to the bathroom, I picked up my copy of Hofstadter’s GEB and looked again at the FIGURE-FIGURE sequences of Chapter III:

1, 3, 7, 12, 18, 26, 35, 45, 56, 69, …

and

2, 4, 5, 6, 8, 9, 10, 11, 13, 14, …

where the two sequences together contain each of the natural numbers exactly once and the second sequence comprises the differences between the numbers in the first sequence. I love that book; in probably a dozen attempts, I am probably about 5% of the way to the enlightenment it offers.

Your task is to write programs that generate the two sequences. 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.

Pages: 1 2

Some applications of random number generators. games, for instance, require that the random sequence be available to run in reverse.

This is easy to do with a simple linear congruential random number generator, which is characterized by the formula next = a * prev + c (mod m). With a little bit of algebra, that formula can be written prev = a−1 * (next - c) (mod m), where a⁻¹ is the inverse of a (mod m); that modular inverse always exists because the linear congruential generator requires that a and m are coprime.

Your task is to write a reversible random number generator. 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.

Pages: 1 2

Sorting the lines of a file that fits in memory is a simple matter of loading the file and calling the sort function. When the file doesn’t fit in memory, however, it must be sorted in pieces, then combined into a single output, which is harder.

Your task is to write a program that sorts the lines of a file that is too large to fit into memory into ascending ascii order. 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.

Pages: 1 2

Given a file containing lines of text that fits into memory, it is easy to write the file with lines in reverse order: read the lines of text into memory, then write them in reverse. It is harder to reverse the lines of a file if the file is too big to fit into memory.

Your task is to write a program that reverses the lines of a text file that is too big to fit in memory. 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.

Pages: 1 2

Today’s exercise is a simple file-handling task for beginning programmers: take the name of a text file as input and write as output the first and last lines of the file.

Your task is to write the file-handling program described above. 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.

Pages: 1 2