Name: Md. Mahbubul Hasan

College/University?: Bangladesh University of Engineering and Technology

Course/Major?: Department of Computer Science and Engineering

Degree Program (B.Sc., M, Sc., PhD, etc.) M. Sc.

Email: shanto86@gmail.com

Homepage: Not Available

Availability:
  o How much time do you plan to spend on your GSoC?
	Recently I was busy with my admission into M. Sc. Program. But now I am quite free. I am planning to spend about 30 hours per week in this project.

  o What are your intended start and end dates?
	I want to start working on the project from 9th April, 2011 (GMT+6 time).
	
  o What other factors affect your availability (exams, courses, moving, work, etc.)? 
	Currently I am lecturer at BUET, having 18 hour class period per week. On tuesday I have no class and thursday and friday weekend. So I hope to spend maximum of the time in these days, and also on the other days in regular basis.


Background Information:

Educational Background:
I am Computer Science graduate from Bangladesh University of Engineering and Technology. In our final semester we were given choices for: Hardware group(VLSI), Network group (Data communication, Wireless Network), AI Group (Machine Learning, Pattern Recognition) and Theoretical Computer Science (Algorithm Engineering, Advanced Computational Geometry). I had taken Theoretical Computer Science as my topic. All the basic courses such as, compiler, operating system, network, algorithm, data structure, micro processor, software engineering, database etc were in my courses.

Professional Background:
I did not work for any company.

Interest in Programming:
From high school, I was very interested in programming. I participated in "Asia Pacific Informatics Olympiad 2006" and won silver medal. I also participated in "ACM ICPC World Finals 2008 and 2009".

Interest in Boost:
While coding for programming contest, i used STL which made our life easier and also efficient sometime. But there were many algorithms not implemented in it. So we used to build our own library, where we kept algorithms of different types. We specially made a geometry library where there were some useful functions or algorithms which were very handy during contest time. I did not know about boost library until few weeks back when in a open discussion session one of my friends showed me boost library. Its huge collection interested me a lot. While browsing through last few year's gsoc proposals i found heap as a topic. My undergraduate thesis topic was also related with heap. At that time I learnt about "Soft Heap" which is quite different from other heaps and also very interesting in its nature. So I want to contribute boost library with this little contribution. I also have interest to continue helping implementing many different algorithms after gsoc. I always had interest for open projects but never tried them thinking it would be tough. I think gsoc will clear all my fear and I will be more interested in implementing many other different algorithms for boost.

Have you done any previous work in this area before or on similar projects? 
Well, as I said my undergrad thesis was on heap, so I already studied "Soft Heap". So I hope I will be able to do this project.
No, I have not done any type of similar projects before, but I have the experience to implement straight line drawing of a planar graph and integrate it with the system in our lab.

Please rate, from 0 to 5 (0 being no experience, 5 being expert), your knowledge of the following languages, technologies, or tools:

    * C++: 4
    * C++ Standard Library: 4
    * C++ Standard Template Library (STL to be specific): 5
    * Boost C++ Libraries: 0.5
    * Subversion: 0.5

What software development environments are you most familiar with (Visual Studio, Eclipse, KDevelop, etc.)? 
I am most familiar with Visual Studio in windows environment.
In linux platform, I would prefer Eclipse. I worked on it before and I would prefer to work on eclipse for this project.

What software documentation tool are you most familiar with (Doxygen, DocBook, Quickbook, etc.)? 
I am familiar with none, but I hope it will not take much time to get familiar with them.

Project Proposal:

What is Soft Heap?
According to Chazelle:
"Given any mixed sequence of n operations, a soft heap with error rate e (for any 0 < e <= 1/2) ensures that, at any time, at most en of its items have their keys raised. The amortized complexity of each operation is constant, except for insert, which takes O(log 1/e) time."

Why Soft Heap?
The surprising fact is that, though Soft Heap is unpredictable in nature but it is used to design deterministic algorithms. This data structure is used for selection problem, Minimum spanning tree problem. There are many useful use of Soft Heap described in the paper written by Bernard Chazelle.

My proposal:
There is recent paper by Kaplan and Zwick who proposed "A simpler implementation and analysis of Chazelle's Soft Heaps". 
1. I want to find cons and pros of the two different methods by Chazelle and Kaplan.
2. Implementing both the algorithms for the boost library. 
3. After implementing the data structure, I want to also implement some of the applications to test the "Soft Heap" against the perfect result to these applications.
4. Compile a documentation.

Plus point: I have good contact with Professor Dr. M. Kaykobad and Dr. Masud Hasan who are very good at heap. Professor Kaykobad has over 20 publications on heaps. If there is any problem regarding the heap, I can easily seek help from them.

Milestone and Schedule:
April 9 - April 30: Understanding Boost Library, Capturing coding style, Getting familiarized.
May 1 - May 14: Communication with Mentor for proper guidance and continue exploring Boost Library if necessary.
May 15 - May 21: Analyzing Chazzel's Soft Heap and make a small report of the findings.
May 22 - June 5: Implementation and Testing of Chazzel's Soft Heap
June 6 - June 12: Analyzing Kaplan's Soft Heap and make a small report of the findings.
June 13 - June 25: Implementation and Testing of Kaplan's Soft Heap
June 26 - July 11: Refine the works for Mid term evaluations.
July 12 - July 15: Refine the works for Mid term evaluations if necessary.
July 16 - July 31: Implementing and testing at least two applications. [I will try my best to start implementing applications before mid-term evaluation]
August 1 - August 10: Learning documentation procedure
August 11 - August 18: Preparing Documentation for Soft Heap
August 19 - August 25: Polishing and Brusing the entire project.

Relevance with the existing library files and some note:
So far what I found out is that, fibonacci_heap.hpp file is closely related with this project. The "Soft Heap" structure is like "Binomial Heap" which is very closely related with "Fibonacci Heap". So I am now going through this specific file along with other boost library files to understand overall mechanism. As I am new in these types of projects so I cant but take some time to understand the entire library. I believe I wont take much time in implementation and testing once I have good idea about boost library.

Previous implementation:
I found no relavant work in STL or any other websites or libraries.

Conclusion:
Finally I would like to thank Boost community for creating and continuously working by polishing, fixing bugs, implementing new algorithms, writing documentations. It would be a great opportunity to contribute into Boost library. I also like to thank google for organizing Google Summer of Code for encouraging young generations to get involved into open source community.

Reference:
1. Wikipedia: Soft Heap (http://en.wikipedia.org/wiki/Soft_heap)
2. The Soft Heap: An Approximate Priority Queue with Optimal Error Rate by Bernard Chazelle
3. A Simpler implementation and analysis of Chazelle's Soft Heaps by Kaplan and Zwick