GSoC draft proposal: Heaps & Queues library
This is only a draft, not the final proposal. Personal Details: Name: André Martins Ferreira Email: greiskul@gmail.com 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.
I am interested in Heap algorithms too. Whom should I contact with? On Sun, Mar 21, 2010 at 7:39 PM, Andre Ferreira <greiskul@gmail.com> wrote:
This is only a draft, not the final proposal.
Personal Details: Name: André Martins Ferreira Email: greiskul@gmail.com 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
Personal Details: Name: André Martins Ferreira
Hi André, Thanks for the draft proposal. Unfortunately, I would have to say that this proposal doesn't really demonstrate a thorough understanding of the problem. It re-states many of the assertions or claims made in the project ideas page, but doesn't expand on them. Why are the existing heaps and queues insufficient? Why do you think this is a good project for Boost? What, specifically, are you proposing to do about it? You might here [1] for ideas on improving your proposal. Andrew Sutton andrew.n.sutton@gmail.com [1] https://svn.boost.org/trac/boost/wiki/SoCHints
participants (3)
-
Andre Ferreira -
Andrew Sutton -
Liang Dong