Morris Counting

February 20, 2015

We have today an algorithm from the early days of computing that is still relevant today: counting a large number of events using only a small amount of memory. The technique was invented by Robert Morris (early unix researcher and NSA cryptographer, father of the RTM of “internet worm” fame) and described in his 1978 paper
“Counting Large Numbers of Events in Small Registers.”

The basic idea is to count logarithms instead of discrete events. Assuming base-2 logarithms, the algorithm is simple:

Initialize a counter C to 0.

When an event occurs, increment the counter with probability 2C.

When asked for the count, return 2C − 1.

It probably seems like a trivial saving to record a count in a single byte instead of, say, a 4-byte integer. But the savings multiply quickly if you need to count a large number of distinct events; the difference between 1-megabyte and 4-megabytes of counters could be significant in a large program where counting is only a small part of the whole.

Your task is to write a program that does Morris counting. 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

Invoice

February 17, 2015

Today’s exercise comes from a text for a first-level programming course.

          Praxis Grocery Store
               17 Feb 2015

1  2% Milk               2  3.30    6.60
2  93% Ground Beef       1  5.98    5.98
3  Clam Chowder          2  1.78    3.56
4  Honey                 1  4.42    4.42
5  6 Eggs                1  1.18    1.18
   Subtotal                        21.74
   Tax 5.25%                        1.14
   Total                           22.88

Your task is to write a program that prompts the user to enter item descriptions, quantities and amounts and produces an invoice as shown 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 3

Closest Pair, Part 2

February 13, 2015

In a previous exercise we studied the brute-force method for finding the closest pair of points in a set of points by forming all pairs, computing the distance between each of them, and choosing the smallest. That algorithm has time complexity O(n2). Today we will look at a divide-and-conquer algorithm that has time complexity O(n log n.

The divide-and-conquer algorithm sorts the pairs along their x-coordinates, splits the list of pairs in two, recursively finds the closest pair in the two halves, then compares all points for the closest pair that crosses the dividing line between the two sets of points, taking the minimum of the three possibilities. The third possibility is the tricky one. It won’t do to consider all possible pairs. Instead, we consider only those points less than d distance from the dividing line, where d is the minimum of the distances of the two recursive calls. It can be proved, though we won’t do so here, that the third step takes only linear time, so the entire algorithm is O(n log n).

Your task is to write a program that computes the closest pair of points in an input set using the divide-and-conquer 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.

Pages: 1 2 3

Project Euler Problem 1

February 10, 2015

Project Euler is a collection of math problems intended for computer solution, and is one of the inspirations for Programming Praxis. The first problem on Project Euler, which also regularly appears on lists of phone interview questions, asks you to:

Find the sum of all the multiples of 3 or 5 below 1000.

Your task is to write a program that solves Problem 1 for arbitrary n; since the problem is simple, you must provide at least three fundamentally different solutions. 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 provides two questions involving selection from a stream. Both require a solution that takes O(n) time and O(1) space.

First: Given a stream of unknown length, select a random item from the stream, with all items selected with equal probability. For instance, given the stream {A, D, F, A, G} the selection would return A with probability 40% and D, F or G with probability 20%.

Second: Given a stream of unknown length, each item in the stream paired with a weight, select a random item from the stream with all items selected with probability according to their weights. For instance, given the stream {1 A, 2 D, 5 F, 3 A, 9 G} the selection would return A with probability 20%, D with probability 10%, F with probability 25%, and G with probability 45%.

Your task is to write the two programs that select items from streams. 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

Closest Pair, Part 1

February 3, 2015

Today’s exercise comes from the field of computational geometry; given a set of points in two-dimensional space, find the pair with the smallest distance between them. The simple solution uses brute force to calculate the distance between all pairs, taking time O(n2).

Your task is to write a program that calculates the closest pair of points. 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

M4 Macros

January 30, 2015

I’ve always had a love/hate relationship with m4 macros. For programming languages that don’t offer macros, or have only a limited form of macros (like C), m4 can be a godsend. Used to their fullest potential, m4 macros enable programmers to write programs that write programs, which can lead to extremely high productivity. And m4 macros aren’t limited to use in programming; I used m4 macros recently when writing my security camera essay (which is what inspired me to write this exercise).

If you’re interested in learning about m4, the original tutorial by Brian Kernighan and Dennis Ritchie is a fine introduction for casual use, the manual for Gnu m4 is complete and definitive, and this short essay by Ken Turner is a little bit insane.

Your task is to use m4 to write some program or transform some text; the purpose is to introduce you to m4 (or re-introduce you if it’s been a long time since your last use), so any task will do. 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

Sum Of Four Primes

January 27, 2015

Today’s exercise comes from one of those competitive programming websites. I never participate in the coding frenzy at those sites, because the competitiveness at extracting every last millisecond from the run time or deleting every unneeded character from the program text ruins the pleasure, but some of the problems are fun:

Given a positive integer 7 < n ≤ 10000000, find four prime numbers with sum n. For instance, 46 = 11 + 11 + 17 + 7.

Your task is to write a program to find four primes that sum to n. 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

Fibonacci Conjecture

January 23, 2015

The sequence of Fibonacci numbers is defined as F0 = 0, F1 = 1, Fn = Fn−2 + Fn−1. It has been conjectured that for any Fibonacci number F, F2 + 41 is composite.

Your task is to either prove the conjecture to be true or find a counter-example that demonstrates it is false (hint: this is not a blog about proving math theorems). 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

Largest Forward Difference

January 20, 2015

In an array of integers, the forward difference between any two elements is the rightmost integer less the leftmost integer. The largest forward difference is the greatest value of all forward differences between elements of the array. If there are no positive forward differences, the largest forward difference is taken to be zero, as if an integer is subtracted from itself.

For instance, in the array [1,5,7,2,9] the largest forward difference is 9 – 1 = 8, and in the array [4, 3, 2, 1] the largest forward difference is 0.

Your task is to write a program that finds the largest forward difference in an array. 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

Follow

Get every new post delivered to your Inbox.

Join 655 other followers