Re: [boost] Contributing in the algorithm library

Subject: Re: [boost] Contributing in the algorithm library
From: mohammad sharique (1sharique1_at_[hidden])
Date: 2018-01-21 15:42:35

Hello all,
I was going through Suryans's proposal and there were several things that I
wanted to discuss:

> >>> > I want to get a head start on how to add new modules in algorithm
> >>> library
> >>> > of boost.
>

1) Since, the algorithms library is only for "general purpose algorithms" (
http://www.boost.org/doc/libs/1_61_0/libs/algorithm/doc/html/index.html), I
am afraid that data structures like Segment Tree, Fenwick Tree, Suffix
array, Suffix Tree may not find its place in this module. However, Zeta
Function, given its application in string matching can definitely be added
to it, in addition to KMP that we already have there.

2) However, I think Segment Tree, Suffix Tree can very well be added to
Boost.Intrusive library [
http://www.boost.org/doc/libs/1_64_0/doc/html/intrusive/reference.html] (as
it has many querying applications), reason being that this library's main
objective is to provide an interface for the complex and intrusive seeming
data structures. [Infact, I see querying data structures like treap and
splay tree already being present, which itself indicates that the above two
can find its place too]. However, there's a need to define the algorithms
for several different use-cases whose solution can be retrieved efficiently
using Segment Tree(for instance). In short, a solution interface for its
application.
       For Surayans: If you need help, please don't hesitate asking for it.
I'd be glad to help :)

3) However, I'm not sure if Fenwick Tree can be included to it, as in
general it is very easy to implement(non intrusive and serves almost the
same purpose as segment tree, although it uses much lesser space that
segment tree)

4) Also about Polynomial Hashing, I don't know for sure but I think it
definitely might have been included in some hash-specific library (and
ofcourse with better hash techniques/algorithms). So imho, I don't see any
particular reason to be included.

5) Now with regards to Lowest Common Ancestor algorithm, I don't see a
point of it being included in algorithms library without an interface for
tree already being present in there, internally. However, I think it might
be relevant to Boost.Graph library.

Also I have some ideas to propose, now that we talk about Boost.Intrusive
(which seems pretty interesting)  we can have some tree related
optimisations techniques and algorithm which are pretty complicated to
implement, and well follow in line with intent of having this module.
1) Adding Heavy-Light Decomposition(HLD) technique. It has got some really
good applications in real world. Some can be found here:
https://wikivisually.com/wiki/Heavy_path_decomposition#Applications
2) Centroid Decomposition Techniques, which has, in recent past become a
very popular optimisation technique for query related problems on trees.

[As a side note, when we implement either of above two, we'll anyway be
needing LCA algorithml. So it may also find its proper use.]

I think these two ideas, apart from the previous few can make a good 3
month project. I would love to hear views on the same, and if it sounds
good I'd be glad to mentor the project.