David Smith

I am a programmer. I live in Gilbert, Arizona. I analyze and visualize data. I write algorithms, system software, and applications.

I like Forth for its commitment to simplicity, clarity, and parsimony. I also use Unix-style tools such as Linux, Python, and C. To some extent I can work with Windows and applications from Microsoft. 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

Languages

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.

Problems

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.

Teaching

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