top | item 30677740 (no title) Royi | 4 years ago Is there a paper or a post which describes the solution? discuss order hn newest nalrey|4 years ago I just want to mention that these algorithms were known way back and it is sad that the authors of CRAN package do not acknowledge it in their docs:1. O(NK^2) dynamic programming from 1965 by James Bruce (https://dspace.mit.edu/bitstream/handle/1721.1/4396/RLE-TR-4...)2. O(KNlogN) dynamic + divide&conquer algorighm from 1989 from Xiaolin Wu and John Rokne (http://doi.acm.org/10.1145/75427.75472)3. O(NK) algorithm from 1991 by Xiaolin Wu (http://dx.doi.org/10.1016/0196-6774(91)90039-2) Royi|4 years ago Is there any implementation in Python / Julia / MATLAB? nerdponx|4 years ago Yes, the R package was written by the authors of the paper, and the CRAN info page references the paper.
nalrey|4 years ago I just want to mention that these algorithms were known way back and it is sad that the authors of CRAN package do not acknowledge it in their docs:1. O(NK^2) dynamic programming from 1965 by James Bruce (https://dspace.mit.edu/bitstream/handle/1721.1/4396/RLE-TR-4...)2. O(KNlogN) dynamic + divide&conquer algorighm from 1989 from Xiaolin Wu and John Rokne (http://doi.acm.org/10.1145/75427.75472)3. O(NK) algorithm from 1991 by Xiaolin Wu (http://dx.doi.org/10.1016/0196-6774(91)90039-2) Royi|4 years ago Is there any implementation in Python / Julia / MATLAB?
nerdponx|4 years ago Yes, the R package was written by the authors of the paper, and the CRAN info page references the paper.
nalrey|4 years ago
1. O(NK^2) dynamic programming from 1965 by James Bruce (https://dspace.mit.edu/bitstream/handle/1721.1/4396/RLE-TR-4...)
2. O(KNlogN) dynamic + divide&conquer algorighm from 1989 from Xiaolin Wu and John Rokne (http://doi.acm.org/10.1145/75427.75472)
3. O(NK) algorithm from 1991 by Xiaolin Wu (http://dx.doi.org/10.1016/0196-6774(91)90039-2)
Royi|4 years ago
nerdponx|4 years ago