Many problems in algorithm design can be specified in two parts, one defining a broad class of solutions (the "easy'' part) and the other requesting one particular such solution, optimal in some sense (the "hard'' part). This dichotomy is nicely captured by Galois connections (GC) in which one of the adjoints delivers the optimal (hard) solution. We show how the algebra of GCs can be used to reason about such algorithms independently of their implementation, and introduce a binary relational combinator whereby such implementations can be calculated using the (relational) algebra of programming. The approach extends results previously known for so-called "greedy'' and "dynamic'' programming in a way which makes them more systematic and easier to apply. (joint work with Shin-Cheng Mu, Academia Sinica, Taiwan) |