May 28, 2010
A useful utility program is one that neatly prints a file or set of files, often a program listing, with each page labelled with filename and page number and each file starting on a new page.
That program turns out to be somewhat tricky to write. In ancient times, before laser printers, most output was to dot-matrix printers using fan-fold paper, and it was amusing to see programs that couldn’t count lines correctly, so the output drifted up and down on successive pages. Another common error of file printers is to print a useless blank page after a file that exactly fills the previous page.
Your task is to write a program that neatly prints a file or set of files. 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.
May 25, 2010
The Stanford GraphBase of Donald Knuth provides a portable, high-quality random number generator called GB_FLIP. Based on the lagged fibonacci generator an = (an-24 − an-55) mod m, GB_FLIP provides values on the range zero inclusive to 231 exclusive, has a period of 285 − 230, and the low-order bits of the generated numbers are just as random as the high-order bits. You can read Knuth’s original version of the program at http://tex.loria.fr/sgb/gb_flip.pdf.
Your task is to write your own version of GB_FLIP. 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.
May 12, 2010
Wow. Now I know the secret to getting lots of page hits and reader comments.
Thanks to all who sent their best wishes in comments and private emails. It’s comforting to know that so many of you care. Thanks also to Remco for posting exercises in my absence. Still, though I appreciate your words, what would really make me feel good is for you to solve an exercise and post the solution.
I’ve been home for a day now, and I’m fine. The blood clots are completely dissolved, and my blood chemistry is nearly correct to prevent future clots — another few days of medication and blood tests should get it exactly right. I’ll be returning to work next Monday, and I’ll likely return to blogging the week after that.
May 9, 2010
I write this from my hospital bed, where I am recovering from blood clots in both lungs; my right lung was 100% blocked, my left lung 60%. I am doing well, and expect a complete recovery.
However, I will not be blogging for a while, probably for two to four weeks. Until I resume, your task is to visit Programming Praxis every Tuesday and Friday morning and do any exercise you have not yet done; I want to see those comment queues filling up.
May 7, 2010
The integer logarithm of a number n to a base b is the number of times b can be multiplied by itself without exceeding n.
The implementation of the
ilog function in the Standard Prelude recently changed. The old version looked like this:
(define (ilog b n)
(if (zero? n) -1
(+ (ilog b (quotient n b)) 1)))
That takes time O(n) as it repeatedly divides by b. A better version takes time O(log n) as it brackets the logarithm between two possible values then uses bisection to calculate the solution.
Your task is to write a program that calculates the integer logarithm of a number to a given base in time O(log 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.
May 4, 2010
Steven Skiena has written a book, The Algorithm Design Manual, that is justly a favorite of Programming Praxis; it is an encyclopedia of common algorithms and data structures, with many pointers to original sources. Recently, I have been reading Skiena’s book, Calculated Bets, which describes a computer program, developed by Skiena and his students, for betting on the game jai alai.
Jai alai is similar to handball, played by teams of one or two players who alternately catch the ball in a basket worn on their wrist and throw it back to the front wall; a point is won when one team is unable to catch the ball and throw it back before it bounces twice, or for various other technical infractions. Although only two teams compete for each point, there are eight teams playing in a game; the first two teams start the game, with the remaining six teams forming a queue, and after each point the winner of the point scores, the loser goes to the back of the queue, and the first team in the queue competes against the previous winner. Each point has a value of 1 until each team has played once (that is, for the first eight points of a game), when the value of winning a point increases to 2. The team that first reaches seven points is the winner.
The purpose of the rule that increases the value of a point from 1 to 2 is to reduce the bias in favor of teams that start early in the queue (have a low “post position”). But, as Skiena points out, the rule isn’t perfect.
Your task is to write a program that simulates a large number of jai alai games and calculates the average winning percentage for each post position. 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.