November 13, 2007
S-C. Mu. Maximum segment sum is back: deriving algorithms for two segment problems with bounded lengths. In Partial Evaluation and Program Manipulation (PEPM ‘08), pp 31-39. January 2008.
[PDF] [GZipped Postscript]
[More ...]
- 0 Comments
Tags: Program Derivation, Segment Problems.
November 11, 2007
To practise using the Logic.ChainReasoning module in Agda, Josh proved the foldr-fusion theorem, and I thought it would be an small exercise over the weekend to start off where he finished…
[More ...]
- 2 Comments
Tags: Agda, Program Derivation, Segment Problems.
June 20, 2007
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.
[More ...]
- 0 Comments
Tags: Greedy Theorem, Program Derivation, Segment Problems, Thinning Theorem.