Currency Exchange
February 27, 2015
There is much data available on the internet, and it is often convenient to query that data in a specific way, repeatedly. In that case, the best thing to do is to write a program to automate the request. Today’s exercise is specifically about currency exchange, but anything is fair game, from weather reports to baseball standings.
Your task is to write a program that takes a “from” currency, a “to” currency, and an amount specified in the “from” currency, and returns the equivalent amount in the “to” currency. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Coin Flips
February 24, 2015
I decided over the weekend to perform a simple test over several random number generators at my disposal; the test counts the number of “heads” that appear in a million flips. Here’s the test:
(do ((n 1000000 (- n 1)))
(h 0 (if (< (rand 1.0) 0.5) (+ h 1) h)))
((zero? n) h))
Applied to the random number generator built-in to Chez Scheme, I get these five results: 500017, 500035, 499968, 499977, and 500009. That’s pretty close to perfect. The random number generator in the Standard Prelude isn’t as good: 499987, 500503, 500422, 499808, and 500264. And the simple linear-congruential random number generator (69069 x + 1234567) % 232 gives these results: 500301, 499445, 500232, 500047, and 498341.
None of those results are unusual (well, maybe the Chez result is too close to perfection), but that’s not what interests us today. What we want to do is assume that the random number generator is biased but still use it to make an unbiased coin flip. Say you have a coin that returns 40% heads and 60% tails. To get an unbiased coin result, flip the coin twice; if you get two heads or two tails, flip twice more, but if you get opposite results, return the first.
Your task is to write a program that delivers unbiased coin flips from a biased coin. 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.
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 2−C.
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.
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.
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.
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.
Two Stream Selection Questions
February 6, 2015
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.
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.
Programming Praxis 