Re: [boost] Contributing in the algorithm library

Subject: Re: [boost] Contributing in the algorithm library
From: Surayans Tiwari (f2013777_at_[hidden])
Date: 2018-01-22 01:30:08

Hello Sharique,
I didn't knew that ,I should have googled it more. Actually my idea was
inspired by this blog -

http://codeforces.com/blog/entry/18407

Thanks .

On Sun, 21 Jan 2018 at 11:54 PM, mohammad sharique <1sharique1_at_[hidden]>
wrote:

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

-----------------------------------------------------------------------------------------