Hi, I am Mahbub. I am a CSE graduate. I just saw you had a proposal regarding queue and heap in GSoC 2010. In my undergraduate I did thesis on heaps. In that time I learned soft heap, it might be interesting to you. Here is the short description of soft heap<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&type=pdf>.( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.3258&rep=rep1&type=pdf) Soft heap is a heap like data structure but with some uncertainty. This data structure supports insert, delete, merge, findmin. It does every work in amortized constant time except insert operation which takes O( log 1/e ) where 0<e=<.5. Here e is error rate. The data structure will never contain more than en corrupted elements. There are two versions of soft heap. 1. By Binomial Tree 2. By forest of binary tree There is one more thing that might interesting to you. That is, in my undergraduate I improved the running time of heap sort by significant amount by applying pairing technique. The paper is submitted to International Journal of Computer Mathematics and it is under review now. It mainly improves Carlsson's variant of heapsort. It also improves the deletion method proposed by Gonnet and Munro (Heaps on Heaps). [The heap is inplace, that means no additional space is required] It also improves the Weak Heapsort. WeakHeapsort is a sorting method which requires O(n) additional bit to sort. However applying the pairing technique it can be reduced to O(n/2) additional bit. It is known that weakheap is the theoretically best known algorithm. [Best considering number of comparisons] So I am just curious if you are interested in these types of algorithms. I saw no possible proposal category where these fits in, but I thought you might be interested. Please let me know what do you think about this. Mahbub
I am Mahbub. I am a CSE graduate. I just saw you had a proposal regarding queue and heap in GSoC 2010. In my undergraduate I did thesis on heaps. In that time I learned soft heap, it might be interesting to you.
So I am just curious if you are interested in these types of algorithms. I saw no possible proposal category where these fits in, but I thought you might be interested.
Hi, I think this would make a nice summer project. There was work done towards a library of heaps and queues last year. I think that a soft-heap might make a nice addition. I would suggest, as part of your proposal that you survey the design of other soft heap implementations to get ideas for the design. You will also probably want to look at the previous work on heaps and queues. I think a proposal of this nature should address how you plan to integrate with that work. Andrew
Hi, Sorry for taking so much time. I am quite new in such projects. I have tried my best to make a proposal according to your suggestion. I had checked all the relevant materials of "Soft Heap" and also checking the implementation of other heap in boost library. It would have been great if you could check my draft proposal and let me know if there is any thing to be fixed, or any other thing that I have to write elaborately. Thanking you, Mahbub On Tue, Mar 29, 2011 at 7:17 PM, Andrew Sutton <asutton.list@gmail.com>wrote:
I am Mahbub. I am a CSE graduate. I just saw you had a proposal regarding queue and heap in GSoC 2010. In my undergraduate I did thesis on heaps. In that time I learned soft heap, it might be interesting to you.
So I am just curious if you are interested in these types of algorithms. I saw no possible proposal category where these fits in, but I thought you might be interested.
Hi,
I think this would make a nice summer project. There was work done towards a library of heaps and queues last year. I think that a soft-heap might make a nice addition.
I would suggest, as part of your proposal that you survey the design of other soft heap implementations to get ideas for the design. You will also probably want to look at the previous work on heaps and queues. I think a proposal of this nature should address how you plan to integrate with that work.
Andrew
Hi, I have shared the proposal in google doc. I also uploaded it at scribd, here is the link: http://www.scribd.com/doc/52429532 Mahbub On Wed, Apr 6, 2011 at 3:35 AM, Andrew Sutton <asutton.list@gmail.com>wrote:
It would have been great if you could check my draft proposal and let me know if there is any thing to be fixed, or any other thing that I have to write elaborately.
Can you post a link to a PDF of the file?
Andrew
Hello, Here is the proposal<http://www.google-melange.com/gsoc/proposal/review/google/gsoc2011/mahbub/1>that I submitted into gsoc site (melange) Please let me know if you have any suggestion Mahbub On Wed, Apr 6, 2011 at 11:46 PM, mahbubul hasan <shanto86@gmail.com> wrote:
Hi, I have shared the proposal in google doc. I also uploaded it at scribd, here is the link: http://www.scribd.com/doc/52429532
Mahbub
On Wed, Apr 6, 2011 at 3:35 AM, Andrew Sutton <asutton.list@gmail.com>wrote:
It would have been great if you could check my draft proposal and let me know if there is any thing to be fixed, or any other thing that I have to write elaborately.
Can you post a link to a PDF of the file?
Andrew
Here is some update regarding the proposal: Extended Proposal: There will be a unit test to check the correctness of the implementation. The reference for the unit test module can be: "/boost_1_46_1/libs/range/test/algorithm_test". We will test our algorithm varying error rate and check if we are getting the output as we expect. We need to monitor the following facts: 1. error rate 2. individual minimum, maximum and average time of each operation (push, extract, delete) The applications that can be implemented as a part of project is listed below in the order of priority: 1. Median in Linear time. 2. Selection algorithm (Reference: Wikipedia) 3. Dynamic Maintainance of grades (reference: chazzele's paper). We can make a documentation explaining how it can be done using soft heap. 4. Minimum spanning tree, and check the performance between soft heap version MST and general MST Mahbub On Fri, Apr 8, 2011 at 3:19 AM, mahbubul hasan <shanto86@gmail.com> wrote:
Hello,
Here is the proposal<http://www.google-melange.com/gsoc/proposal/review/google/gsoc2011/mahbub/1>that I submitted into gsoc site (melange)
Please let me know if you have any suggestion
Mahbub
On Wed, Apr 6, 2011 at 11:46 PM, mahbubul hasan <shanto86@gmail.com>wrote:
Hi, I have shared the proposal in google doc. I also uploaded it at scribd, here is the link: http://www.scribd.com/doc/52429532
Mahbub
On Wed, Apr 6, 2011 at 3:35 AM, Andrew Sutton <asutton.list@gmail.com>wrote:
It would have been great if you could check my draft proposal and let me know if there is any thing to be fixed, or any other thing that I have to write elaborately.
Can you post a link to a PDF of the file?
Andrew
participants (2)
-
Andrew Sutton -
mahbubul hasan