Segment Problems
Calculating a linear-time solution to the densest segment problem
Sharon Curtis and Shin-Cheng Mu. Calculating a linear-time solution to the densest segment problem. Journal of Functional Programming, Vol. 25, 2015.
[Paper (doi: 10.1017/S095679681500026X)| Supplementary Proofs | Code]
The problem of finding a densest segment of a list is similar to the well-known maximum segment sum problem, but its solution is surprisingly challenging. We give a general specification of such problems, and formally develop a linear-time online solution, using a sliding window style algorithm. The development highlights some elegant properties of densities, involving partitions that are decreasing and all right-skew.
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.
The Windowing Technique for Longest Segment Problems
Reviewing Zantema’s “windowing” technique for computing the longest segment of the input that satisfies a suffix-closed predicate.
Longest Segment Satisfying Suffix and Overlap-Closed Predicates
Translating Zantema’s work to Bird-Meertens style, to compute the longest consecutive segment of the input that satisfies a predicate that is suffix and overlap-closed.
On a Basic Property for the Longest Prefix Problem
Giving a constructive proof for one of the essential properties in Hans Zantema’s Longest Segment Problems.