Elsie Four
March 27, 2018
It’s been a while since we did any cryptography. Alan Kaminsky developed an algorithm that he claims is suitable for hand operation but is also quite secure. You can read about the cipher and Kaminsky’s cryptanalysis of it at the link.
Your task is to implement Kaminsky’s Elsie Four cipher. 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.
Stable Sort
March 23, 2018
A sorting algorithm is stable if items with equal keys appear in the output in the same order they appear in the input. In many cases the stability of a sorting algorithm doesn’t matter; in other cases it is critical. Some sorting algorithms, such as merge sort, are inherently stable (unless you muck up the implementation), which other sorting algorithms, such as quick sort, are inherently unstable. It is always possible to turn an unstable sort into a stable sort by adding an index to the data and using the index to break ties.
Your task is to write a program that converts an unstable sorting algorithm into a stable sorting 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.
Television Time
March 20, 2018
Today’s exercise is an interview question:
There is a room with a television and people come in and out of the room to watch it; the television is on only when there is at least one person in the room. For each person that enters the room, we record the start and end time, represented as a two-element array containing the starting time (inclusive) and ending time (exclusive), with times as integers (you can think of hours, or minutes, or any interval you like). We want to know how long the television is on. For instance, given the list of intervals (1 4), (6 8), (2 4), (7 9), the television is on at times 1, 2, 3 from the first interval, times 6 and 7 from the second interval, times 2 and 3 from the third interval, and times 7 and 8 from the first interval, a total of 6 times the television is on (at times 1, 2, 3, 6, 7 and 8).
Your task is to write a program that takes a list of intervals and returns the number of times at which the television is on. 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.
Mid-Term Exam
March 16, 2018
At many colleges and universities, Spring Break is approaching soon, and that means mid-term exams are also imminent. Here are two questions suitable for a mid-term exam for not-too-advanced students:
First: You are given two strings, say “aet6ukm” and “123678”; neither is necessarily sorted. You are to find the first character in the first string that also appears in the second string, and return the index of the character in the second string. For the two strings above, the character “6” appears in the first string and also in the second string, at index position 3 (counting from zero), so your program should return 3.
Second: You are given a list of recipes, where each recipe is a list with a name in the first position of the list and a list of ingredients in the remaining positions of the list; for instance, (“Pasta” “Spaghetti” “Tomato sauce” “Basil”) is a simple recipe for pasta. Your program should return a list of all ingredients that are used in more than one recipe, with a list of recipe names attached to each ingredient.
Your task is to answer the two mid-term exam questions given 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.
Nearest Pair
March 13, 2018
Today’s exercise is an interview question:
You are given a list of integers and must find the nearest pair that sum to a given target. For instance, given the list (1 5 3 6 4 2), if the target is 7, there are three pairs with the required sum, (1 6), (5 2) and (3 4), but pair (1 6) has two intervening numbers, pair (5 2) has three intervening numbers, and pair (3 4) has only one intervening number, so (3 4) is the nearest pair.
Your task is to write a program to find the nearest pair. 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.
Array Rotation, Timing Tests
March 9, 2018
We have been looking at Section 2.3 of Jon Bentley’s book Programming Pearls in the last two exercises, and have implemented his “juggling” and “block swap” algorithms. Bentley also discusses a third algorithm, which he calls the “reversal” algorithm, and which we implemented several years ago. Bentley goes on to give timing comparisons between the three algorithms.
Your task is to generate timing comparisons similar to Bentley’s, to see what happens with your system, your language and your compiler. 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.
Array Rotation, Again
March 6, 2018
In Section 2.3 of his book Programming Pearls, Jon Bentley gives three O(n) algorithms for rotating an array. We looked at the first algorithm in the previous exercise; today we look at the second algorithm:
A different algorithm results from a different view of the problem: rotating the vector x is really just swapping the two segments of the vector ab to be the vector ba, where a represents the first i elements of x. Suppose a is shorter than b. Divide b into bl and br, so that br is the same length as a. Swap a and br to transform abrbr into brbla. The sequence a is in its final place, so we can focus on swapping the two parts of b. Since this new problem has the same form as the original, we can solve it recursively. This algorithm can lead to an elegant program, but it requires delicate code and some thought to see that it is efficient enought.
As before, Bentley challenges us to implement the rotation algorithm and he gives a cryptic hint: “How does the greatest common divisor of i and n appear in the program?”
Your task is to implement the array rotation algorithm 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.
Array Rotation
March 2, 2018
I’ve been re-reading Jon Bentley’s book Programming Pearls. In Chapter 2, Section 2.3, Bentley discusses the problem of rotating the elements of an array (for instance, rotate the array abcdefgh three positions left to defghabc) in time proportional to the length of the array using only a small, constant amount of extra space, and he gives three algorithms for doing so. Today’s exercise discusses the first. Here’s Bentley’s description:
One successful approach is a delicate juggling act; move x[0] to the temporary t, then move x[i] to x[0], x[2i] to x[i], and so on (taking all indices into x modulo n), until we come back to taking an element from x[0], at which point we instead take the element from t and stop the process. If that process didn’t move all the elements, then we start over at x[1], and continue until we move all the elements.
Then Bentley challenges us to implement the rotation algorithm, and he gives a cryptic hint: “How does the greatest common divisor of i and n appear in the program?”
Your task is to implement Bentley’s array rotation 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.
Seven-Segment Devices
February 27, 2018
We have today a simple exercise from Jon Bentley’s book Programming Pearls, Chapter 3, Problem 8:
[S. C. Johnson] Seven-segment devices provide an inexpensive display of the ten decimal digits:
----- ----- ----- ----- ----- ----- ----- ----- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ----- ----- ----- ----- ----- ----- ----- | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | ----- ----- ----- ----- ----- ----- -----The seven segments are usually numbered as:
--2-- | | 3 4 | | --1-- | | 5 6 | | --0--Write a program that displays a 16-bit positive integer in five seven-segment digits. The output is an array of five bytes; bit i of byte j is one if and only if the ith segment of digit j should be on.
It was harder to type those digits than it looks.
Your task is to write a program to display numbers using seven-segment digits, as Bentley directs. 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.
I Think I’m Crazy!
February 23, 2018
In a recent exercise I wrote about a shell script I am writing at work. Development of the shell script continues, as I work my way through the various requirements of the script. At one point, I decided to use Awk to process a piece of the task, and I had to look something up in the Awk manual, and while I was there I noticed that Gawk has a -M option to use gmp for the arithmetic, giving Awk a big-integer capability. So it occurred to me: awk big integers … prime numbers … awk big integers … prime numbers … and so a project was born.
I decided to write a prime number generator in Awk, based on this previous exercise. Never mind that Awk doesn’t provide iterators, I ought to be able to figure this out. And I did; the result is on the next page. For the record, it works. But it’s horribly slow; generating the 78498 primes less than a million takes about four-and-a-half seconds, which is at least four seconds too long. Am I crazy?
Your task is to tell us about something crazy you have done, writing a program in a language that doesn’t provide what you need, either because you were forced to do so by circumstances or because you wanted to be crazy, as I did. 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.
Programming Praxis 