Re: [boost] GSoC draft proposal: Heaps & Queues library

Subject: Re: [boost] GSoC draft proposal: Heaps & Queues library
From: Liang Dong (serendipity0306_at_[hidden])
Date: 2010-03-22 13:58:44

I am interested in Heap algorithms too. Whom should I contact with?

On Sun, Mar 21, 2010 at 7:39 PM, Andre Ferreira <greiskul_at_[hidden]> wrote:

> This is only a draft, not the final proposal.
>
> Personal Details:
>        Name: André Martins Ferreira
>        Email: greiskul_at_[hidden]
>        University: Universidade Federal do Rio Grande do Sul <
> www.ufrgs.br >
>        Course: Computer Science
>        Degree Program: Bachelor of Computer Science
>        Availability: About 30 hours a week will be devoted to the project,
> more if nescessary.
>                                  Start Date: April 1st
>                                  End Date: not yet decided
>                                  Factors of influence: I live in the
> Southern Hemisphere, so the
> Summer of Code will be during Winter. While I will have
>                                  a winter vacation where my attettion will
> be 100% devoted to the
> project, it will only last about a month, from July to August.
>                                  During the rest of the time I will study
> in the morning, and
> work on the project on my free time, which luckily this semester
> entails
>                                  all afternoons. I have worked during
> school time in previous
> semesters, and know that it's possible.
>
> Background Information:
>        I am a brazilian computer science student, my course has 9
> semesters,
> I am currently in the 7th. I have been programming for the last 5
> years, mostly in C++
> but also in Scheme, Lua, and many other languages. I've had an
> intership in developing parallel programs using MPI, and more recently
> in supporting an
> ERP written in C++.
>        My main interest is in algorithms and data structures, but I'm also
> interested in functional programming languages.
>        My experience with heaps comes from my university classes, Cormen's
> Introduction to algorithms book, various online sources and personal
> experimentation.
>        While I have implemented heap data structures before (binary,
> binomial, skew), I have never integrated them in a single package
> generic package before
> and I'm looking foward to learn from it.
>        I would rate my experience in the following technologies this way:
>                4   C++
>                4   C++ Standard Library
>                2   Boost C++ Libraries
>                3   Subversion
>        I use mainly Eclipse and Geany for development, but I have also done
> projects with Visual Studio.
>        For documentation I prefer to use Doxygen.
>
> Purpose and goal:
>        Heaps are very useful data structures and are used as building
> blocks
> in many algorithms.
>        There are some heap data structures implemented in boost, for use in
> Boost.Graph for example,
> but at the moment they are coupled with the library they support.
>        This project's goal is to decouple them into a boost/heaps library,
> cleaning them up where needed,
> and completely rewritting them if nescessary. All heaps will provide a
> common interface where possible,
> allowing algorithms writters to quickly change the data structure they
> are using without further changes to their code.
>        The complexity of every operation on every heap will be documented,
> and tested to ensure correctness.
>        A priority queue wrapper like std::priority_queue will also be
> provided.
>        Heaps structures that will be provided: binary, binomial, fibonnaci,
> mutable heaps, suggestions are welcomed.
>
> Proposed Milestones and Schedule (work in progress):
>        Binary heap implemented and submitted, possibly on top of STL heap
> algorithms, to have some foundation for the rest of the work,
> allowing tests on the other data structures to be compared to a simple
> but correct heap implementation.
>        Moving heap structures from /boost/pending to the heap library,
> adapting them to a common interface and cleaning up where nescessary.
> No rewrites.
>        Binomial Heap implementation.
>        If any of the heap structures from pending were deemed unfit,
> rewritting them.
>
> This proposal is still under work, but I would like feedback from the
> community, not only on the project but also in the proposal itself.
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>