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

Gödel Numbering

January 16, 2015

Gödel numbering is a system that assigns a natural number to each symbol and expression in a logical system, invented in 1931 by Kurt Gödel for the proofs of his incompleteness theorems. Consider the logical system where symbols are letters and expressions are words; for instance, the word PRAXIS consists of six symbols P, R, A, X, I, and S. Gödel numbering would assign numbers to the letters, say A=1 … Z=26, then assign each letter as the exponent of the next prime, so PRAXIS would be numbered 216 × 318 × 51 × 724 × 119 × 1319 =

83838469305478699942290773046821079668485703984645720358854000640

The process is reversible; factor the Gödel number and decode the exponents.

Your task is to write functions that encode strings as Gödel numbers and decode Gödel numbers as strings. 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 have today our fourth essay: Building a Security Camera with a Raspberry Pi. An essay isn’t an exercise; it doesn’t present a task for you to perform, but instead provides extended discussion and complete source code. Though essays may be based on exercises, the idea is that an essay can delve more deeply into a topic than is possible in the limited space and time of an exercise.

My daughter recently had a thief enter her apartment and steal her laptop computer. Later, when I asked her what she wanted for Christmas, her answer was immediate: a security camera, so in case she is robbed again she will have pictures of the thief to give to the police. But commercial security cameras are expensive, often several hundred dollars, and many are tied to security services with expensive monthly fees, which she wasn’t interested in paying. So I built a security camera using a Raspberry Pi, and wrote this essay describing how I did it.

Please read the essay, and feel free to comment on it below; comments on the essay itself are closed. Let me know if you see any errors. And feel free to link to the essay on the internet if you know of places where it is appropriate.

One-Time Pad

January 9, 2015

In a previous exercise Ben Simon showed us how to use a trigraph for secret communication. For illustration, he used a one-time pad based on a simple random number generator, but that is not sufficient for proper cryptographic secrecy. In today’s exercise we build a secure one-time pad.

We need two things. One is a cryptographically-secure source of random bits. Solutions include counting the clicks of a geiger counter or reading the background radiation, but being a software guy rather than a hardware guy I suggest the Blum-Blum-Shub cryptographically-secure random number generator of a previous exercise. The second is a way to convert bits to letters. The method we choose is to take 26 consecutive bits from the Blub-Blub-Shum generator, form them into a number, and take the result mod 26, discarding the four largest numbers from the set in order to make all letters equally likely to be chosen, which is similar to the calculation of a previous exercise. Given those two things, it is easy to generate random letters and build a pad of any desired size.

Your task is to write a program to generate one-time pads. 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

Lucas-Carmichael Numbers

January 6, 2015

We start the new year with a simple task from number theory. A Lucas-Carmichael number is a positive composite integer n, odd and square-free, such that p + 1 divides n + 1 for all prime factors p of n. For instance, 2015 is a Lucas-Carmichael number because 2015 = 5 × 13 × 31 and 5 + 1 = 6, 13 + 1 = 14, and 31 + 2 = 32 all divide 2015 + 1 = 2016. The restriction that n be square-free prevents the cubes of prime numbers, such as 8 or 27, from being considered as Lucas-Carmichael numbers.

Your task is to write a program to find all the Lucas-Carmichael numbers less than a million. 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 678 other followers