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 18:24:21

Hi,

> 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
> .
>

Actually we can query hash for any substring/subarray after we apply
polynomial hash, without using inverse module. I'd suggest to look it up.
Also, imho it is way too trivial to be included separately. Do you have any
particular reason to include it?

Regards,
Sharique

On Sun, Jan 21, 2018 at 9:29 PM, Surayans Tiwari <
f2013777_at_[hidden]> wrote:

> 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
>
> ------------------------------------------------------------
> -----------------------------
>