David Smith

I am a programmer in Missoula, Montana. I have a Ph.D. in mathematics (combinatorics, graph theory). I analyze and visualize data. I write algorithms and applications. Here is a recent project on industrial automation. I recommend Forth. I have also worked with Unix-style tools such as Linux, Bash, Awk, and C.

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. For a code sample, open the PostScript version of my resume in a text editor such as Vim.

Programming tools I use

Languages

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. Often I get by without special database management software, as it is easy to do random file access in C and build indices with Bash, Awk, and sort.

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. There is broad appeal in the graphics. The evaluation model is simple and fun. 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.

Agile is dumb

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.

If you can describe what your team does only in terms of people, you are screwing up.

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.

Problems I tried to solve

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 some 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: