Boost logo

Boost :

Subject: Re: [boost] Contributing in the algorithm library
From: Surayans Tiwari (f2013777_at_[hidden])
Date: 2018-01-21 15:59:53


Thank you for going through my proposal. Hld and centroid decomposition
will really be a good addition and I have also worked on them before.
My entire idea of including polynomial hashing was , even if he take a low
prime number to hash like 2 , then also we won't be able to hash a string
of length greater than 63 because long long is of size < 2^64 , so in every
case we will be calculating hash modulo a prime number , now if we want to
find the value between a range in the string then we have to apply modulo
inverse , we can't directly just substract from cumulative array , so I
thought automating everything in the library will be a really good addition

I have started working on some algorithms and I will ping you if I face
some problem.
Thank you.
On Sun, 21 Jan 2018 at 9:12 PM, mohammad sharique <1sharique1_at_[hidden]>

> 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" (
> 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 [
> (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:
> 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.

*Surayans Tiwari*
M.Sc. (Hons) Chemistry & B.E.(Hons.) Mechanical Engineering
Mobile: +91 8504004392
Email: f2013777_at_[hidden] <f2013586_at_[hidden]>
*Birla Institute of Technology & Science**,* Pilani
Pilani Campus, Rajasthan, INDIA - 333031

Boost list run by bdawes at, gregod at, cpdaniel at, john at