Re: [boost] Contributing in the algorithm library

Subject: Re: [boost] Contributing in the algorithm library
From: Rishabh Arora (rishabharora1997_at_[hidden])
Date: 2018-01-24 09:45:48

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

Best Regards,
Rishabh

On Mon, Jan 22, 2018 at 7:00 AM, Surayans Tiwari via Boost <
boost_at_[hidden]> 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_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_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
>