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
> 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
> 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
> 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
> 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
> 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:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk