For all reports, the intended audience is a first-year graduate student in computer science without electives in your area. Please briefly explain concepts that you would not expect such a student to understand, but that are necessary for understanding your report. Citations, in the standard form for a research paper in computer science, are encouraged.

Identify three potential projects for the class. Ideally, a project should center on analyzing the behavior of a single algorithm or larger system that is already implemented. This could be an algorithm developed by yourself, students or faculty in the department, or researchers at other institutions. The goal of the project should be to understand some behavior of the algorithm or system under varying conditions. For more information about this report, look at an example report

The length of this report should be three paragraphs, one for each potential project.

As we have discussed in class, the behavior of an algorithm (or larger system) is a combination of the algorithm itself, a task, and an environment. For example, the behavior of a database system depends on aspects of the system (e.g., methods for query optimization), aspects of the task (e.g., the specific queries the system is asked to execute), and aspects of the environment (e.g., disk speed and available RAM).

In this report, describe key aspects of the algorithm/system, task, and environment that you have selected for study. Recall that the algorithm or system is what a computer scientist controls, the task is that a user controls, and the environment is what neither controls.

In the case of the algorithm or system, describe it in sufficient detail that the reader could design an implementation without further information. Note the use of the term design; actual implementation would almost certainly take additional information, but the reader should be able to identify the key components (e.g., classes and methods) necessary for an implementation.

Also, describe the task and environment that you are expecting to study. Identify key variables of the task and environment (e.g., for the database example: query complexity, structure of the database, number of records, available RAM). Note which variables you can directly control and which variables you can only measure but not directly control. Identify and briefly describe key resources that you expect to use in future phases of the project, including benchmark datasets, simulation environments, text corpora, query sets, etc. Note the extent to which these resources provide coverage of the range of the key variables mentioned above.

The length of this report should be approximately 3-4 pages of single-spaced text with additional space for diagrams and citations. Diagrams, tables, and citations are encouraged.

Many important types of research questions can be generated by informal observation of an algorithm's behavior in a "naturalistic" or laboratory setting. Such an approach can identify cases where an algorithm does not perform as expected or it can generate new questions about previously unexplored types of behavior. For example, the decision by Oates & Jensen (1997) to examine the relationship among training set size, tree size, and accuracy is an example of this latter phenomenon.

This type of investigation occupies a middle ground between theorizing (which often does not use empirical data) and formal experimentation (which often focuses on examining a predeterimined question). The goal here is exploratory, so we will use an informal approach to generating and analyzing data.

Run an implementation of your algorithm on multiple instances of your selected task and environment, varying specific aspects of the algorithm, task, and environment in isolation and in combination. Measure and record the values of key variables.

Apply exploratory analysis tools to the data you have generated in an effort to examine how the behavior of your algorithm varies with aspects of the task and environment. Identify unexpected behavior or new combinations of variables that you had not previously considered important.

The length of this report should be at least two pages of single-spaced text with additional space for diagrams and citations. Diagrams and tables are expected.

Many hypotheses about a given algorithm or system can be evaluated based on the published research of other investigators. This literature forms a foundation that should inform your own research plans and investigations. It can provide useful findings, suggest interesting research questions or methods, and eliminate or modify your potential avenues of inquiry.

Examine papers and other published work that is relevant to your algorithm or system. Focus on those papers that provide insight into potential research questions that have emerged from your behavior exploration.

Summarize and synthesize the relevant findings of at least four papers. Explain their findings and briefly describe the relevance of those findings to your own investigations. Identify gaps, oversights, or errors in the published literature. Be sure to provide some overall organization that helps to synthesize, classify, describe, or structure the papers, rather than only providing a recounting of their findings.

The length of this report should be two pages of single-spaced text with additional space for diagrams and citations. Diagrams and tables should be used if needed to convey the results of others or the overall organization of the literature. Complete bibliographic citations are expected.

Research proposals have an obvious "external" purpose. They explain potential research to others who might provide necessary resources, permission, or assistance. However, they have an "internal" purpose as well. They encourage you to examine the larger purpose of your research, to clarify the questions you are seeking to answer, and to plan your research in ways that can anticipate potential pitfalls.

Decide a single research question that you wish to examine regarding your algorithm or system. Examples of research questions from papers we have read in class include: "What effect does increasing training set size have on tree size?", "What are the properties of difficult constraint satisfaction problems?", and "Do decentralized market-based algorithms perform better than centralized algorithms?" Explain why your research question is at the frontier of current knowledge by positioning it within the existing research literature.

Identify one or more falsifiable hypotheses that help address your research question. Again, each hypothesis should be falsifiable --- a statement about your algorithm or system that is capable of being disproven by some conceivable experimental evidence. Identify each hypothesis as either existential, compositional, correlational, or causal. Strive, if possible, to identify at least one causal hypothesis.

Briefly outline one or more possible experiments that you could run to attempt to falsify each hypothesis. Do not describe the experiments in detail (that will be done in a subsequent report). However, do describe why the experiment is both stringent (i.e., would be likely to falsify the hypothesis if it is really false) and reliable (i.e., likely not to falsify the hypothesis if it is really true).

This report should be a minimum of two pages of single-spaced text. Call out the research questions and hypotheses clearly by using italics, bold, or indented text.

Careful experimental design can lead to more efficient research. It can reduce the need to re-run experiments whose flaws are only discovered posthoc, and it can identify potential improvements that lead to more useful and powerful experiments.

Describe the hypothesis or hypotheses that you intend to evaluate. Describe the variables of the algorithm, task, environment, and behavior that you will measure in the experiment, including their basic category (dependent, independent, or randomized) and what units you will use to measure them. Finally, describe the experimental protocol you will use to obtain measurements and how you intend to analyze the results.

Recall that you do not need to evaluate a large number of hypotheses or variables. You should select one or two key hypotheses and a small number of variables, based on your behavioral exploration, information from the existing research literature, and your own intuitions.

Also, the experiments that you describe here do not constrain your choices in the next few weeks. If, upon further experimental work, the experiments you outline here do not yield interesting results, you can deviate substantially from this description. This report is merely intended to identify the most likely avenue of investigation.

This report should a minimum of two pages of single-spaced text. Diagrams and tables are encouraged where appropriate.

Report 6: Experimental Results

Briefly review the hypotheses that your experiments are intended to evaluate and the experimental design used. Where the experimental design deviated from your previously stated design (Report 5), note the difference.

Present the results of the experiments in such a way that the reader can infer their own conclusions from the results, but also present the high-level conclusions that you believe should be drawn from the results. Discuss how the results differ from, or are consistent with, your expectations before the experiment. Discuss the substantive significance of your results, and apply statistical significance tests, where appropriate.

This report should a minimum of two pages of single-spaced text. Graphs and tables of results should be used frequently, to supplement textual descriptions of results.

Report 7: Final Report

Combine the materials in Reports 1 through 6 into a single unified document that describes: 1) The algorithm, task, and environment studied; 2) The state of existing knowledge about the algorithm and its behavior; 3) The research question and specific hypotheses examined; 4) The experimental design employed; and 5) The experimental results obtained.

This report should a minimum of ten pages of single-spaced text. Graphs, diagrams, and tables should be used where appropriate. References should be provided in some standard form at the back of the document. Appendices with detailed results can be added after the references if needed.