# Program Derivation

## Programming from Galois connections — principles and applications

Shin-Cheng Mu and José Nuno Oliveira. Programming from Galois connections — principles and applications. Technical Report TR-IIS-10-009, Academia Sinica, December 2010.
[PDF]

## Programming from Galois connections

Shin-Cheng Mu and José Nuno Oliveira. Programming from Galois connections. In the 12th International Conference on Relational and Algebraic Methods in Computer Science (RAMiCS #12), LNCS 6663, pages 294-313. May 30 – June 3, 2011.
[PDF]

## Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning

Shin-Cheng Mu, Yu-Han Lyu, and Akimasa Morihata. Constructing datatype-generic fully polynomial-time approximation schemes using generalised thinning. In the 6th ACM SIGPLAN workshop on Generic programming (WGP 2010), pages 97-108, Sep. 2010. [PDF]

## Evaluating Simple Polynomials

I had a chance to show the students, in 25 minutes, what functional program calculation is about. The student have just been exposed to functional programming a week ago in a three-hour course, and I have talked to them about maximum segment sum way too many times.

## Sum of Squares of Differences

Given an array of integers having at least two elements, compute the sum of squares of the difference between all pairs of elements. It is not hard to quickly write up a `O(N²)` program using nested loops, which, I have to confess, is what I would do before reading Kaldewaij’s book and realised that it is possible to do the task in linear time using one loop.

## An Exercise Utilising Galois Connections

In the recent work of Sharon and me on maximally dense segments we needed quite a number of functions to be monotonic, idempotent, etc. It only occurred to me after submitting the paper: could they be defined as Galois connections?

## Finding Maximally Dense Segments

Sharon and I have finally concluded, for now, our work on the maximally dense segment problem (download the draft here), on which we have been working on and off for the past two years. Considering the algorithm itself and its derivation/proofs, I am quite happy with what we have achieved. The algorithm is rather complex, however, and it is a challenge presenting it in an accessible way. Sharon has done a great job polishing the paper, and I do hope more people would be interested in reading it and it would, eventually, inspire more work on interesting program derivations.

## Functional pearl: maximally dense segments

Sharon Curtis and Shin-Cheng Mu. Functional pearl: maximally dense segments. Submitted.
[PDF]

## The Maximum Segment Sum Problem: Its Origin, and a Derivation

In a previous paper of mine, regrettably, I wrongly attributed the origin of the maximum segment sum problem to Dijkstra and Feijen’s Een methode van programmeren. In fact, the story behind the problem was told very well in Jon Bentley’s Programming Pearls.

I learned the function derivation of the maximum segment sum problem from one of Jeremy’s papers and was very amazed. It was perhaps one of the early incident that inspired my interest in program calculation.

## Maximally Dense Segments — Code and Proof

Code and proof accompanying our forthcoming paper Functional Pearl: Maximally Dense Segments.