This project combines my vocation (teaching computer science) with an avocation (working on a shareware genealogy database, Gene).

Although the bulk of Gene consists of uninteresting manipulation of data, various odd corners of the program (particularly its the user interface code) involve nontrivial algorithmic techniques. If interesting algorithms turn up here, they could turn up anywhere. So I am creating these pages as a showcase for the applications theoretical algorithms have as parts of a real-world application.

- Problem: center text accurately using
space and option-space characters.

Solution: an integer linear program closely related to Euclid's algorithm for GCD. - Problem: quickly find the
shortest connections between a given pair of people, for "Relations"
tree drawing.

Solution: backtracking search (implemented) or translation to a k-shortest-paths problem on a much larger graph (theoretical).

- Problem: look up and alphabetize a dynamically changing set of
names.

Solution: splay trees. - Problem: search for substrings of names.

Solution: Knuth-Morris-Pratt string matching. - Problem: wrap text to fit into narrow columns in tree
drawings.

Solution: a linear time dynamic program. - Problem: adjust widths of columns in tree drawings and
recompute the total tree width.

Solution: rake-compress trees. - Problems: speed up scrolling and redisplay of tree
drawings;

quickly translate mouse clicks to active regions of drawings.

Solution: interval trees.

Gene, David Eppstein, ICS, UC Irvine