David Smith

I am a programmer. I live in Gilbert, Arizona. I analyze and visualize data. I write algorithms, system software, and applications. Here is a project on industrial automation. I recommend Forth for its commitment to simplicity, clarity, and parsimony. I also use Unix-style tools such as Linux, Bash, Python, Awk, and C. To some extent I can work with Windows and applications from Microsoft. For example, I have written desktop applications in Python that run on Windows systems.

In 2009 I confirmed by a construction of Kierstead and Trotter that the performance ratio of the first-fit algorithm for coloring interval graphs is at least 5.

On the other hand, a method of Pemmaraju, Raman, and Varadarajan can be used to show that the ratio is at most 8. It's exciting to make progress toward knowing this constant of graph theory. People have been curious about it for many years now. Professor Trotter has a page on first-fit coloring of interval graphs.

My resume is a PostScript program typed by hand into a text editor. PostScript is not just a document format, but a programming language. You can run PostScript programs with Ghostscript, produce PDF with ps2pdf, and produce SVG with Inkscape.

Programming tools I use


Forth is the best choice. This essay by Jeff Fox recommends Forth to young programmers. Starting Forth by Leo Brodie is a good introduction to Forth (and programming in general) available online. JONESFORTH by Richard M.W. Jones is nicely annotated (first read jonesforth.S, then jonesforth.f).

Sometimes my solutions involve cooperating programs in several languages. It has been many years since I have needed a database management product. Usually it is easier to do random file access in C; build indices with Bash, Awk, and sort; and keep backups.

For visualization I have used Graphviz, SVG (viewable in Firefox), and PostScript. For graphic user interfaces I have used GTK+ and Python's Tkinter (Tk) module.

I like the Small Combinatorial Library of Dan "sigfpe" Piponi written in Haskell. An entry on surjections at MathOverflow gives another demonstration of how useful mathematics can be in answering questions that arise in programming.

Rarely do I hear of people programming in PostScript, but you could teach it to beginners. Graphics programming is fun. The evaluation model is simple. The PostScript Language Tutorial and Cookbook is easy to find. On many Linux systems, you can type PostScript commands into the default text editor; output shows up in the file browser; and if you open the file there, you get an output window that's automatically refreshed when the file is saved. Is there a simpler development environment?

Operating systems

If Forth is unavailable, Linux is usually a practical choice. I have used FreeBSD, SunOS, Solaris, and IRIX. Open-source software is desirable. Eventually you find the system or library you are using to be missing a feature. You want to add it by messing around, figuring things out, and reading the web, not by calling some corporation's technical support line or hiring expensive consultants. Sometimes with commercial software these are your only options. It's easy and fast to collect and install all the tools a programmer needs on a Linux system. If you want to deal with a corporation, you still can.

Software development methodology

People working together, if they want to be efficient, divide responsibility so that they communicate (which involves waiting) only when necessary. A software development methodology that has regular meetings as a key ingredient is just dumb. That's Agile. Agile is dumb. More on that in a minute.

If you are building software, you are trying to create a program that runs on machines to complete some task. One person can do this work. Many people can do this work. Software is not about the number of people working, or their roles, or the nature of their communication. Programming is usually easy once the task is well defined, and until the task is well defined, the programs you write may not be useful. Adding people or meetings doesn't help. You should organize your efforts around defining the task.

A proven strategy is to define a modest task and expand it incrementally. You don't have to write a specification before programming begins, as in the "but waterfall" argument of the Agile enthusiasts. But you do have to write a spec, and this responsibility, if assigned to a group of people, belongs at the top of a hierarchy, not in a system of meetings among stakeholders.

In practice, Agile means frequent meetings and no documents, both bad ideas. Is this intentional? Let's read the Manifesto. They favor...

Agile.1: Individuals and interactions over processes and tools.

Let me get this straight. You can describe what you do in terms of people, not things, and you are an expert in automation?

Agile.2: Working software over comprehensive documentation.

With Agile, people write the documentation they feel like writing. Usually it's none, and that's too little. Before Agile, software worked most of the time and people fixed bugs and wrote new features. With Agile, it's the same, but no one can say exactly what the software does.

Agile.3: Customer collaboration over contract negotiation.

Great idea! Don't deliver anything specific.

Agile.4: Responding to change over following a plan.

False choice. Do both or lose! When change comes, adjust the plan. If you respond to change without a plan, you lose the advantage of your strategic assets.


In 2004 I worked on ITA Software's Palindromic Pangram challenge. The goal is to construct a string of words from a certain English dictionary so that
  1. each letter of the alphabet appears at least once, and
  2. ignoring spaces, the string is a palindrome.
This turns out to be easy. The challenge is to produce a string with the fewest letters. No palindromic pangram can be shorter than 51 letters (twice 26, less 1). My best results in 2004 were 65 letters long. I have found shorter ones. Here are a couple of my 61-letter palindromic pangrams: Other people have done still better. Apparently ITA has retired the palindromic pangram problem. It is archived with others like it here. I have solved Strawberry Fields.

Project Euler is great. I have solved around 160 problems. I recommend it to students. However, (1) sometimes you have so many apples that before you eat them all, you are tired of apples, and by apples, I mean diophantine equations. (2) The site is addressed to those "for whom the basic curriculum is not feeding their hunger to learn." That's fine, but I would have had trouble understanding and solving many of these problems without my institutional experience. Thank you to my teachers.

Project Euler: dacvs

Books I like

I recommend: For young readers: I do not recommend Calculus: Single Variable by Hughes-Hallett and others. I wish schools would stop using it. There are many good books on calculus. I like Apostol's Calculus, but it may be hard to find at a low price. If you are a student looking for a calculus textbook, try your school's library, or that of a nearby university. Don't be afraid of the old, ragged books.


I taught university mathematics for years (here I discuss my time at GVSU). I agree with these:

In support of free speech

We should be free to speak without fear of punishment from the government. When the government goes too far, we should point it out. See for yourself whether the government went too far in the case of Count Dankula. In Count Dankula's video "M8 Yer Dugs A Nazi" (YouTube), is he (a) inciting hatred of Jewish people, or (b) making a joke to annoy his girlfriend, as he explains in the video itself? Clearly (b), but a British court found him guilty.