You will work in self-selected groups of two to three students. Students must work in groups—no individual projects will be accepted. If you are without a group by the first project deadline, you will be assigned to one of the two-student groups. (Note: Groups cannot exceed three students, so if you wish to avoid the possibility having your group dynamics disrupted, I advise you to form a group of three). You and your team members will evaluate group participation at the project’s conclusion. Your group will receive a single project grade, but your individual course grade can be affected by the results of your team members’ evaluations.

The project has four deadlines.

Oct. 25: Topic and Group Selection due. You must meet with me prior to this date to discuss your ideas for the project and get your topic approved.

Nov. 6: Outline or Draft due. Hand in a hardcopy outline or rough draft of your work. Include an outline of your planned analyses and expected results. I will evaluate only the high-level ideas and organization, not your writing. The goal of this deadline is to make sure you are headed in the right direction.

Nov. 20: Complete First Draft due. Hand in a hardcopy draft of the paper. You will be graded using the same grading form that will be used for your final paper, so the more complete the draft and the more technical work you have completed, the more points you will receive. At a minimum, background material should be in near-final form, and you should have at least one set of benchmark results done. Ideally, you will have completed most of your technical work. You can then receive an evaluation of the quality of your data analysis and spend the following weeks revising technical work, following up on questions raised by your results, and improving the presentation of your data and analysis.

Dec. 7: Final Paper due. Hand in both a hardcopy and an electronic version. Email the electronic version to me as an attachment named LASTNAME1- LASTNAME2- LASTNAME3.FORMAT. The hardcopy version of your paper will be returned with comments.

Overall, the project will count for 15% of your grade, or 150 points. The draft is worth 50 points and the final paper is worth 100 points. The outline is not graded, though failure to provide an outline for your project will reduce your total score on the paper by 10 points.

This project comprises two components: (1) the algorithm and data structures research and (2) the paper. Science is not done in a vacuum—for the work you do to have value, it must be communicated to colleagues. You will be graded both on the quality of your scientific work and on the quality of your written paper.

The remainder of this handout provides information to guide you in choosing a project and conducting your research. An accompanying handout, Guide to Writing a Successful Paper on an Analysis of Algorithms and Data Structures, offers advice on writing the paper. Additional resources are available at the Cain Project Web site:

http://www.owlnet.rice.edu/~cainproj/courses/comp482.html.

If you are engaged in original research or are working on creating new algorithms, this project is a marvelous opportunity to begin developing a publishable paper. Please consult me to discuss your research and verify its relevance to the course.

If you aren’t engaged in original research, you should still aim to produce a publication-quality analysis of the algorithms or data structures that you examine. The uniqueness and difficulty of your project will factor into your overall grade. You do not need to select algorithms covered in the textbook or even in this course. Because the assignment is to compare algorithms, however, be sure that the algorithms you select are solving the same problem. It is fine to compare well-known algorithms (e.g., you might compare dictionaries as implemented by red-black trees, skip lists, and splay trees). You may also use new algorithms or hybrids of existing ones, provided that you thoroughly describe them in your paper.

To guide and organize your research, be sure your topic has a goal: a hypothesis that drives your project. For instance, you might investigate how well an algorithm with lower asymptotic bounds, but higher constant costs, works with realistic data sets. Or you might research how much an algorithm can be improved by optimizing its memory use, including cache and virtual memory effects.

As your team implements, works with, and runs the various algorithms being studied, you will need to document carefully the choices made so that others can duplicate lost results should a crisis occur. Some of the elements that should be tracked include the following:

Focus your research and the paper on benchmarking and analysis, as this is the bulk of your original work.

The quality of your analysis (how well you explain what you observed, consider what these observations mean, and address questions raised by the results you obtain) is the most important aspect of this project.

Think about these guidelines as you plan this portion of the project:

Determine what data needs to be included in your paper to make your case. Try to select the results to highlight before you write, so that you can devote time to working on how to present them.

Please see the Guide to Writing a Successful Paper on an Analysis of Algorithms and Data Structures on the Cain Project web site to plan your work on documenting your project and leading the class with your paper.