COMP 540 Project

Overview

The pedagogical goal of the project is to be a miniature version of a ``real'' research project. You will first pick a topic, and argue in a research proposal that this is a topic worth exploring, and that you are capable and prepared to do so. You will design and implement a solution to the problem you have chosen, and measure the performance of your solution. You will then write up the results of your project in a draft final report, which, after review, you will turn into a final report. Finally, you will give a 30-minute presentation of the results of your project in class. I emphasize that this is a ``research project'', and not a ``programming project''. Although the implementation of your solution is an essential component, it is only one aspect of the project, next to other equally important components, such as the evaluation and the presentation of your results. The learning curve in these projects could be quite steep, and there is a significant danger of following what turns out to be a dead-end alley. In order to try to alleviate these problems, I will assist you throughout the term to make sure that you continue to make progress,You should use this resource (i.e., me) wisely, remembering however that you are to do the work. In particular, you should regularly update me on the status of your project, for instance, on a bi-weekly basis.

Requirements and Timetable

• [January 17] Project groups formed (groups of at most two).
• [January 31] Project proposal on your project web page (send me the URL!).
• [February 14] Project progress report 1 on your project web page.
• [February 28] Project progress report 2 on your project web page.
• [March 13] Project progress report 3 on your project web page.
• [March 27] Project progress report 4 on your project web page.
• [April 10] Project progress report 5 on your project web page.
• [April 17] Draft of final project report on your project web page.
• [April 22] Final project presentations.
• [April 23] Final project report on your project web page.

Note that the draft final report is due a week before the end of the semester! The project proposal should be no longer than 5 typeset pages. The final report should be no longer than 15 typeset pages.

Reports

Project Proposal

I suggest the following format, from which, of course, you may deviate to suit your particular needs.

• [Abstract] The essential aspects of your proposal.
• [Problem Statement] A clear statement of the problem to be solved.
• [Motivation] Some background and motivation indicating that this is a problem worth solving.
• [Hypothesis] The solution you propose to the problem, with some preliminary justification.
• [Method] The method by which the solution is going to be evaluated. Be specific: state which measurements you intend to make, what you expect to learn from them, etc.
• [Expected Results] Be specific about the results you expect to obtain. If you have some preliminary results, state them. If you are doing an experiment, try to make an educated guess at what the results will be. For instance, if you are going to measure average time to solve instruction scheduling problems, it is much better to say ``We estimate solving a benchmark instruction scheduling problem will require 3000 random restarts of GSAT'', than to say ``We will report the results of measuring times for solving instrucion scheduling problems''. Of course, nobody is going to hold you to your estimates. Nevertheless, discrepancies between estimates and results are often the source of an interesting discussion.
• [Related Work] Relate other work to what you have done.
• [Timetable] Give some convincing arguments why you believe you are able to carry out the project in the remainder of this semester.

Intermediate Progress Reports

The main reason for the intermediate progress report is to ensure that you work steadily on the project. This report can be informal, and must be made available on your project web site. It should concisely state what you have already achieved, what you plan to accomplish, what problems you have encountered, etc. I will use these reports to help guide your work on the problem.

Final Report

The final report should follow essentially the same format as the proposal. The problem statement and motivation sections would typically be grouped into a single introduction section. The section on expected results should be replaced by a section containing the results you obtained, with some discussion. The timetable should be deleted and replaced by a section containing conclusions and avenues for further work.

Writing Proposals and Reports

I expect professionally done documents, without spelling errors, with appropriate references, etc. I suggest the use of the LaTeX text processing system. pdflatex converts Latex files to pdf, which you can place on your project web page. If you have never written a technical document before, you should seriously consider reading one of the standard references on the subject. Each one of these books has its own idiosyncracies. I recommend, if only for its conciseness, ``The Elements of Style'', by Strunk and White, Macmillan Publishing Co. The papers that we read in class might also serve as examples.

In Hindsight

Comp 540 has had similar projects in the past. The following is a summary of the most common weaknesses encountered.

• Major problems often result from starting excessively late. Programs that barely work, a lot of details left unattended or poorly handled, etc.
• You should put a lot of effort into the proposal. Doing so will identify early on the major hurdles on the way to completion of the project, and give you a good assessment of their difficulty and the time it will take you to conquer them. Past experience shows that the degree to which a group has thought out their proposal is a very good predictor of their overall performance on the project.
• People always underestimate the amount of time it takes to ``write up'' the results. You should realize that ``writing up'' includes not only the physical writing, but also and, more importantly, digesting the results. Often, in writing, people come across ``things they should have looked at''. Therefore, start writing early. Some groups find it useful to continue to update their proposal as they go along, leaving them with a good first cut at the final report when they are done with the bulk of the programming. This strategy will give you time to look at such things before it is too late.
• The report is at much too low a level. You should abstract from your implementation those things that you think the reader will find interesting. Again, this is a research project, and not a programming project. You should think of your report as an article you send in to be published, not as a description of work done for a course. For instance, particular names of routines and data structures are of no use. The underlying method is, as are its results.
• The performance measurements are unintelligible. Before you make measurements, you need to determine what it is that you want the measurements to show. Write a paragraph at the beginning of your ``results'' section answering this question. Then, structure your measurements and their presentation accordingly. Results need to be presented in a scientific way. You need to describe exactly how you performed the experiments, such that a knowledgeable person could reproduce them. Make sure your measurement results include units, and, if possible, average values and standard deviations. Moreover, you would like to give the reader some idea of why the results are the way they are. This usually requires a bit more instrumentation, rather than just measuring the program's running time.
• Vacuous prose (especially in the abstract). Examples are: ``Our performance study shows that a reasonable speedup can be obtained.'' , ``Also discussed are insights into which classes of problems would benefit in performance from distribution.'' ,``Several follow-up ideas are presented.'' ,``We also include descriptions of optimizations made and their effects.''. Rather than this kind of vacuous prose, say what speedups were achieved, what were the insights gathered, what were the follow-up ideas, etc. If you cannot present those in a concise abstract, it is probably the case that you have not been able to digest the problem to the point of discerning the important results of your work.
• Statements of the form ``We believe that ..'', followed by the authors' favorite preconception, are inappropriate in a paper. They are appropriate for a proposal, but in a paper they should either be substantiated by evidence or discarded.
• Avoid ``cuteness'' in writing.
• The abstract should stand by itself. It should not rely on or refer to any other document, including the rest of the paper.
• Related work section is meant to em relate your work to that of others, not to give a mere summary of other work.

Project Suggestions

Please make an appointment with me to discuss potential project ideas.

Acknowledgement: This document was written by Willy Zwanepoel for Comp 520 and has been used with permission for Comp 540.