Proving the Thinning Theorem by Fold Fusion
Prove the thinning theorem by fold fusion. Horrifyingly, I could not do it anymore! Have my skills become rusty due to lack of practice in the past few years?
Prove the thinning theorem by fold fusion. Horrifyingly, I could not do it anymore! Have my skills become rusty due to lack of practice in the past few years?
It may be surprising that variations of the maximum segment sum (MSS) problem, a textbook example for the squiggolists, are still active topics for algorithm designers. These literate Haskell scripts presents a program solving two recently studied variations: computing the maximum sum of segments not longer than an upper-bound, and the maximum density (average) of segments not shorter than a lower-bound. 2007/06/26 Update: fixed binary search.
2007/11/04 Update: linear time algorithm for MSDL.
R. S. Bird and S-C. Mu, Countdown: a case study in origami programming. In Journal of Functional Programming Vol. 15(5), pp. 679-702, 2005.
[GZipped Postscript]
S-C. Mu, A Calculational Approach to Program Inversion. D.Phil Thesis. Oxford University Computing Laboratory. March 2003
[GZipped Postscript][PDF]
R. S. Bird, J. Gibbons and S-C. Mu, Algebraic methods for optimisation problems. In Algebraic and Coalgebraic Methods in the Mathematics of Program Construction, LNCS 2297, pp. 281-307, January 2002.
[PDF]
S-C. Mu and R. S. Bird, On building trees with minimum height, relationally. In First Asian Workshop on Programming Languages and Systems, Singapore, December 2000.
[GZipped Postscript]
S-C. Mu, Algebraic Methods for Optimisation Problems. Transfering dissertation.
S. Seres and S-C. Mu, Optimisation problems in logic programming: an algebraic approach. In Proceedings of LPSE’00, July 2000.
[GZipped Postscript]
Programs and profiling results accompanying the paper Countdown: a case study in origami programming. [GZipped Tarball]