Contributing in the algorithm library

older
[outcome] Whether to default EC =...

Surayans Tiwari

15 Jan 2018 15 Jan '18

5:53 a.m.

Hello Boost Community! My name is Surayans Tiwari currently pursuing Bachelors of Engineering at BITS Pilani, India . I am an algorithms enthusiast and c++ programmer with 3 years of experience coding in the language. I want to get a head start on how to add new modules in algorithm library of boost. Please can someone help me with this. Thank you. ‌

Show replies by date

David Bellot

17 Jan 17 Jan

8:53 a.m.

Hi, Excellent idea. Please start writing a short proposal to describe your idea. From that we can help you transforming it into a real proposal. Best regards, David On Mon, Jan 15, 2018 at 5:53 AM, Surayans Tiwari via Boost < boost@lists.boost.org> wrote:

...

Hello Boost Community!

My name is Surayans Tiwari currently pursuing Bachelors of Engineering at BITS Pilani, India . I am an algorithms enthusiast and c++ programmer with 3 years of experience coding in the language. I want to get a head start on how to add new modules in algorithm library of boost. Please can someone help me with this.

Thank you.

‌

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

Surayans Tiwari

9:38 a.m.

Hello David , Thanks for your kind reply ! I will soon write a breif proposal . I was also thinking of making it a gsoc project . Thank you. On Wed, 17 Jan 2018 at 2:24 PM, David Bellot via Boost < boost@lists.boost.org> wrote:

...

Hi,

Excellent idea. Please start writing a short proposal to describe your idea. From that we can help you transforming it into a real proposal.

Best regards, David

On Mon, Jan 15, 2018 at 5:53 AM, Surayans Tiwari via Boost < boost@lists.boost.org> wrote:

...
Hello Boost Community!

My name is Surayans Tiwari currently pursuing Bachelors of Engineering at BITS Pilani, India . I am an algorithms enthusiast and c++ programmer with 3 years of experience coding in the language. I want to get a head start on how to add new modules in algorithm library of boost. Please can someone help me with this.

Thank you.

‌

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

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

1:55 p.m.

Hello David! Here is my brief proposal of what I want to do in gsoc 2018. PFA. Thank you. ‌ *-----------------------------------------------------------------------------------------* *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 ----------------------------------------------------------------------------------------- On Wed, Jan 17, 2018 at 3:08 PM, Surayans Tiwari < f2013777@pilani.bits-pilani.ac.in> wrote:

...

Hello David ,

Thanks for your kind reply ! I will soon write a breif proposal . I was also thinking of making it a gsoc project .

Thank you.

On Wed, 17 Jan 2018 at 2:24 PM, David Bellot via Boost < boost@lists.boost.org> wrote:

...
Hi,

Excellent idea. Please start writing a short proposal to describe your idea. From that we can help you transforming it into a real proposal.

Best regards, David

On Mon, Jan 15, 2018 at 5:53 AM, Surayans Tiwari via Boost < boost@lists.boost.org> wrote:

...
Hello Boost Community!

My name is Surayans Tiwari currently pursuing Bachelors of Engineering at BITS Pilani, India . I am an algorithms enthusiast and c++ programmer with 3 years of experience coding in the language. I want to get a head start on how to add new modules in algorithm library of boost. Please can someone help me with this.

Thank you.

‌

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

--

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

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

David Bellot

21 Jan 21 Jan

12:25 p.m.

Another nice proposal. Seems to be quite ambitious and focus on algorithms, which I like a lot. We'd love to have a mentor for this project. On Wed, Jan 17, 2018 at 1:55 PM, Surayans Tiwari < f2013777@pilani.bits-pilani.ac.in> wrote:

...

Hello David!

Here is my brief proposal of what I want to do in gsoc 2018. PFA.

Thank you. ‌

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

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

On Wed, Jan 17, 2018 at 3:08 PM, Surayans Tiwari < f2013777@pilani.bits-pilani.ac.in> wrote:

...
Hello David ,

Thanks for your kind reply ! I will soon write a breif proposal . I was also thinking of making it a gsoc project .

Thank you.

On Wed, 17 Jan 2018 at 2:24 PM, David Bellot via Boost < boost@lists.boost.org> wrote:

...
Hi,

Excellent idea. Please start writing a short proposal to describe your idea. From that we can help you transforming it into a real proposal.

Best regards, David

On Mon, Jan 15, 2018 at 5:53 AM, Surayans Tiwari via Boost < boost@lists.boost.org> wrote:

...
Hello Boost Community!

My name is Surayans Tiwari currently pursuing Bachelors of Engineering at BITS Pilani, India . I am an algorithms enthusiast and c++ programmer with 3 years of experience coding in the language. I want to get a head start on how to add new modules in algorithm library of boost. Please can someone help me with this.

Thank you.

‌

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman /listinfo.cgi/boost

--

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

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

mohammad sharique

3:42 p.m.

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

3:59 p.m.

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.

mohammad sharique

5:46 p.m.

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

mohammad sharique

6:24 p.m.

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 .

...

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

22 Jan 22 Jan

1:30 a.m.

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

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

Rishabh Arora

24 Jan 24 Jan

9:45 a.m.

Hello Surayans, David asked me to talk to you regarding the details of your proposal. I was his mentee in GSoC '17. Your proposal looked really interesting to and I'd like to work with as a mentor on the project. I wanted to discuss with you before putting it your project on the wiki-tracker. You can get in touch with me on my e-mail: rishabharora1997@gmail.com. Best Regards, Rishabh On Mon, Jan 22, 2018 at 7:00 AM, Surayans Tiwari via Boost < boost@lists.boost.org> wrote:

...

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

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

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/ mailman/listinfo.cgi/boost

2498

Age (days ago)

2507

Last active (days ago)

List overview

Download

10 comments

4 participants

participants (4)

David Bellot
mohammad sharique
Rishabh Arora
Surayans Tiwari