Here are the source files for some short programs I've written which may be useful or interesting to others. Please don't use them for your homework solutions. For one thing, you might flunk. I'm not a professional programmer, and don't even play one on T.V. These represent the best work I can do, but hopefully not the best work you can do.

• The towers of hanoi. A classic elementary programming exercise in recursion.

• Boxtext: A little utility for printing text in a box. The text can be given on the command line or read from stdin. You can use this to spiff up your interactive shell scripts.

• Implementation of the Euclidean Algorithm. The Euclidean Algorithm is an elementary algorithm for finding the greatest common divisor of two numbers.

• A template for processing command-line arguments. This is basically an elaboration of the stuff in section 5.10 of K&R. Supports option arguments, combining single-letter options, and using -- to denote the end of options.

• Miles, a utilty for runners. Prints all combinations of lanes and laps on a track that equal an even number of miles to within a desired tolerance.

• Benford, a program for investigating Benford's Law.

  Benford's law, a curious empirical observation, says that the relative frequency for the most significant digit equaling k is commonly distributed as log((k+1)/k). The story is that the pages near the beginning of the book in old tables of common logarithms were often more heavily worn than pages near the end. Since people usually went to such tables to look up the logarithms of data they observed, this would seem to imply a nonuniform distribution for the most significant digit of the mantissa.

  There is by now a sizable literature on Benford's law. See, for example, T.P. Hill, "The Significant-Digit Phenomenon", Amer. Math. Monthly, April 1995, 322-327, and the references given there.

• A utility to copy over an existing file. In both Unix and DOS the redirection > first truncates the target file to zero length. The redirection >> appends new data at the end of the target file. This program allows new data to be written on top of an existing file starting from the beginning.

• Calculate the expected amount of time to cover (i.e., obtain for the first time) a specified sequence of binary digits in a stream of random digits. (Contains another potentially useful routine, PrintAsDecimal, which prints an arbitrarily long string of 0s and 1s as a base 10 decimal.)

  Algorithm: (pointed out to me by P.Griffin ) If s is the given string of length n Then E T(s) = E T(t) + 2^n, where t is the longest string such that s starts and ends with t. Perhaps surprisingly, the algorithm shows that the expected time is always an integer.

  The algorithm applies much more generally, e.g., to find the expected time to first encounter a given sequence of states in a finite-state ergodic Markov chain. (In that case, 2^n must be replaced by a quantity depending on the transition matrix and stationary probabilities.)

  Also see:

  • Example 4.20, pp 160-161 in S.M. Ross, Introduction to Probability Models 5th Ed., Academic Press, San Diego, 1993

  • G. Blom, On the mean number of random digits until a given sequence occurs, J. Appl. Prob. 19(1982), 136-143.

  • P.T. Nielsen, On the expected duration of a search for a fixed pattern in random data, IEEE Trans. Information Theory 19(1973), 702-704.

  For a proof and other discussion, consult my paper The Expected time to find a string in a random binary sequence.

  Here is a cgi-based demo which accepts only strings of 32 digits or fewer.

• Program to print out examples of the long division algorithm. With the advent of calculators the long division algorithm is quickly becoming a lost art. So that future generations may understand how we suffered in 4th grade, I offer this program. It is capable of solving very large examples.

  Try a cgi-based demo .

• C code for solving Kepler's equation. This code illustrates 5 different methods for solving kepler's equation, a transcendental equation whose solution is one of the key steps in determining the position of a planet or satellite on its orbit. The source code is extensively documented including references to sources for further information.

• An implementation of the bisection method for finding roots of equations. Not an efficient method, but instructive for calculus students studying the intermediate value theorem.

• The definitive leapyear program.

• Calculate the date of Easter and related things.

• A recursive descent parser for translating roman numerals into integers. For the history of roman numerals see pp 242-246 of Number Words and Number Symbols: A Cultural History of Numbers, Karl Menninger (transl. Paul Broneer), MIT press, 1977.

• Tutney

  Tutney is a spelling language which my parents used to communicate with each other when I was a toddler and they didn't want me to be able to follow what they were saying. I am unsure of the origins of tutney. My parents claim it originated in the part of upstate New York where they grew up (Boonville area,) but I have met people from other parts of the world who know tutney. The rules are simple: vowels are pronounced as is, but consonants (except for a few exceptions) are pronounced by doubling the consonant with the letter u interposed. The exceptions are q (prounounced quack), y (pronounced yack), j (pronounced judge), w (pronounced wack), and h (pronounced hash). Surprising proficiency can be attained with a little practise.

  For example, here is a translation of the previous paragraph into tutney. And here is a lex source file for a program to translate English ( or any language using the same alphabet!) into tutney. Here is C language source file for a program to do the same thing. Finally, here is an executable for Windows XP built from the C source. This is a console application. To use it, you would say the following at a command prompt: tutney < source > destination. Or say tutney /h for further usage information.

• A program for studying happy numbers. A happy number n is one with the following property: let f(n) be the sum of squares of the decimal digits of n. The sequence f(n), f(f(n)), ... must eventually fall into a cycle. If the cycle is 1,1,1,..., then the number n is happy. Otherwise it is unhappy. Our program allows different bases and also introduces the concept of an ecstatic number: an ecstatic number is happy in every base up to a certain limit (which measures its ecstasy.) (Also see the Mathematica site for more on this somewhat obscure topic.)

• A program for simulating J. Parrondo's paradoxical game. This involves two games of chance which by themselves are unfavorable, but which when alternated at random become favorable. See J. Parrondo's website for more information.

• A program for printing a nicely formatted pascal's triangle. It is written for simplicity rather than efficiency.

• C source for an implementation of the strstr library routine using the Knuth-Morris-Pratt algorithm. Includes a wrapper main program that allows searching for the first occurrence of a string in a file, printing the failure failure, counting the number of occurrences of a string in a file, and other applications. For further information on the algorithm, consult the paper Knuth, D.E., J.H. Morris, and V.R. Pratt, "Fast pattern matching in strings", SIAM J. Computing, 6:2, 323-350.

• C source for a study of recursive functions. As it stands, this is the world's slowest implementation of the power function. It could easily be extended to give even slower implementations of other, more complex, arithmetic functions.

• A program that writes the set-theoretic definition of ordinal numbers. The sequence of ordinals is defined in terms of the null set, 0, by 0, {0}, {0,{0}}, ...

• A program to search a dictionary for anagrams. The idea for this comes from Programming Pearls, Jon Bentley, 2nd Ed., Addison Wesley, Reading, 2000. Bentley's book is an excellent source of ideas for programming projects.

• A program to print numbers in led style. I.e., like this:

   _               _   _  
   _|   | |_|   | |_  |_| 
   _|   |   |   |  _|   | 
  
  

• A program illustrating several methods for generating all permutations of 1...n. This subject has a large and interesting literature, and this program only begins to scratch the surface. See, e.g., the survey article: R. Sedgewick, Permutation Generation Methods, ACM Computing Surveys 9(1977), 137-164.

• A program to generate pages of random arithmetic problems. Research has shown that mental exercise can help stave off dementia. Use this program to generate a list of random arithmetic exercises with an additional page of answers.

• A program to illustrate a constructive proof of the Schroder-Bernstein Theorem. The proof in question is due to M. Hellman. See, e.g, E. Mendelson, Introduction to Mathematical Logic, 3rd Edition, Wadsworth and Brooks/Cole, Monterey, 1987, pp 198-199.

• A program to tabulate the hypergeometric function. Allows you to vary the parameters and variable at will, and can used either from the command line or in an interactive mode. Output can also be written in XML which links a stylesheet named function_table.css, if it exists. By rolling your own stylesheet you can control the appearance of the tables produced. I intend to use this code as the base for a suite of programs to calculate various special functions if my ambition does not desert me. At any rate, tables of the hypergeometric function are hard to find, so this may fill a need. (This program is very naive. It is only a starting point.)

• Lisper: a program to generate random balanced parenthisis expressions, i.e., things like (()()((()()))). The name is based upon the unoffical reading of the Lisp programming language acronym: Lots of Insipid Silly Parentheses.

• Ackermann: a program to calculate Ackermann's function (as far as that is possible.) The source code hopefully contains instructive comments related to this function and its properties and significance.

• An introspective C program. It prints its own source code listing to stdout. This output could then be compiled and run; that output could be compiled and run .... In essence, it is a very simple, source code level, computer virus. (Addendum: Such programs have been termed "quines" after the logician W. Quine. Apparently the writing of one's own quine is a kind of rite of passage for programmers. See The Quine Page for much more information.)

• A program to demonstrate information packing functions. An information packing function is a function C(x,y) of whole numbers with whole number values which is 1-1. The idea is that such a function packs the information in 2 natural numbers into a single natural number. Suitable extraction functions H ("head") and T ("tail") then retrieve the information via H(C(x,y)) = x and T(C(x,y)) = y. With some care, all 3 functions can be constructed so as to be primitive recursive. The importance of such functions in recursion theory is that they allow functions of several variables to be treated as functions of a single variable. This program illustrates a particularly simple and efficient function C. The idea comes from the beautiful book of Marvin Minsky, Computation: finite and infinite machines, Prentice Hall, Englewood Cliffs, N.J., 1967.

• Compute the Catalan numbers. The source code documents some key points about the theory of these numbers and their uses in combinatorics.

• Euler's totient function. The implementation is highly recursive.

• My own solution to the firing squad synchronization problem. This old problem, attributed to J. Myhill, asks the following: suppose we have n determinisitic finite automata arranged in a line. All the machines have identical state transition diagrams except for the two on either end, which are allowed to be different. The transitions of each machine are allowed to depend on the states of its nearest neighbors, but not on those of any other machine. The machine on the left end is designated "the general." Alone among the machines it has some volition, so that at some time it enters a special state we may call "fire when ready." The problem is to design all the machines so that they will at some point enter a state called "fire" simultaneously. The trick is to make the design independent of n, so that if we inserted an arbitrary additional number of machines in the line, the solution would still work (though it would probably take longer for the machines to synchonize.) My solution is neither efficient nor elegant, but it does seem to work. The code could use lots of polishing, but I can't stand to look at it anymore.

• More to come ... ?