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.