Re: [boost] Contributing in the algorithm library

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

Hello!

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]>
wrote:

> 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.
>
>
-- 
*-----------------------------------------------------------------------------------------*
*Surayans Tiwari*
M.Sc. (Hons) Chemistry & B.E.(Hons.) Mechanical Engineering
Mobile: [phone]
Email: f2013777_at_[hidden] <f2013586_at_[hidden]>
â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„â–„
*Birla Institute of Technology & Science**,* Pilani
Pilani Campus, Rajasthan, INDIA - 333031
-----------------------------------------------------------------------------------------