Re: [boost] Contributing in the algorithm library

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@gmail.com> 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@pilani.bits-pilani.ac.in> 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@gmail.com> 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: +91 8504004392 Email: f2013777@pilani.bits-pilani.ac.in ▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄ *Birla Institute of Technology & Science**,* Pilani Pilani Campus, Rajasthan, INDIA - 333031

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

-- *-----------------------------------------------------------------------------------------* *Surayans Tiwari* M.Sc. (Hons) Chemistry & B.E.(Hons.) Mechanical Engineering Mobile: +91 8504004392 Email: f2013777@pilani.bits-pilani.ac.in ▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄ *Birla Institute of Technology & Science**,* Pilani Pilani Campus, Rajasthan, INDIA - 333031

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