David Smith

Links:

I study graph theory and combinatorics. 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. There's an overview in these slides. 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. There's more information at Professor Trotter's page on first-fit coloring of interval graphs.

Over the years I have taken many university mathematics courses on topics such as:

graph theory
algebraic combinatorics
combinatorial optimization
analysis
algebra
topology
game theory
geometry
set theory.

I've taken courses also in physics, computer science, and chemistry; none in biology.

My work often involves computation. Here I describe tools I use when programming.

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

each letter of the alphabet appears at least once, and
ignoring spaces, the string is a palindrome.

This turns out to be easy, so 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 were 65 letters long. I believe other people have found better solutions, but I have not been able to track them down. Here are some 65-letter palindromic pangrams:

ow verbid tackle gizmo haj up onyx of suq us foxy no pujah om zig elk cat dib rev wo
yak combed sh guv jarl waxy nota quip fez ef piu qat onyx awl raj vughs deb moc kay.

Since that time, I've found some books that I wish I had known about:

Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik;
Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson (thanks, H. Kierstead);
Combinatorial Optimization: Algorithms and Complexity by Papadimitriou and Steiglitz (thanks, G. Hurlbert);
Structure and Interpretation of Computer Programs by Abelson and Sussman.

Apparently ITA has retired the palindromic pangram problem. Some similar problems are still posted, though. Recently I solved Strawberry Fields. I hope that my book list is not considered too big a hint.

Here is one way to reverse a singly linked list in C++.

struct REC {
  int data;
  REC *next;
};

// reverse a singly linked list
REC *reverse(REC *p) {
  /* Make one pass with pointers a,b,c to 3 consecutive records. */
  REC *a = 0;
  REC *c = p ? p->next : 0;
  for(REC *b=p; b; a=b, b=c, c=c?c->next:0)
    b->next = a;
  return a;
}

I'm a member of the American Mathematical Society.

March 2011