Due: Thursday Feb 18, 1999 at the beginning of class
This portion of the report should be between 3-5 pages.

In this part of the assignment, you will select two algorithms for solving the same problem. You report should

• Describe the problem to solved.

• Describe (at a high-level, e.g., in pseudo-code) the two algorithms. You need to give references for the algorithms you select. If they are in the textbook [CLR], then page numbers are sufficient.

• Give a theoretical analysis of each algorithm, including asymptotic running times for best, average, and worst-case inputs (which will require determining, if possible, the format of these inputs). Note: be sure to note what types of operations your theoretical analysis is based on (e.g., comparisons for most sorting algorithms, multiplications for for matrix multiplication algorithms, etc.)

• A theoretical comparison of the two algorithms, indicating when one is desirable over the other.

Due: Tuesday April 20, 1999 at the beginning of class
Your entire write-up (including parts 1 and 2) should be between 8-12 pages, including graphs.

Note: your report for part 2 of the project should include your part 1 as well (revised in accordance with the comments you have received). That is, the initial part of your final report will be the algorithm description and theoretical analysis (part 1), which will be followed by your experimental results and analysis.

In the experimental portion of your report your goal is to thoroughly analyze and understand the actual behavior of the algorithms, to compare their performance, and to relate it to their theoretical analysis. In particular, some of the issues you will need to address in your report are:

• Identifying the appropriate thing to measure: In order to get experimental results you will need to measure something -- usually this will be running time. You need to make it clear in your report what you are measuring and why.

• Choice of Experiments: Describe what experiments you ran, and why you selected them. You will need to argue why they are a good selection of experiments (e.g., you will need to run best, average, and worst-case inputs, for a variety of input sizes, for both of your algorithms. If you don't know the worst-case inputs for your algorithms, then you will need to design experiments to try to determine them).

• Presentation of Results: Looking at long tables of data is not easy to interpret. You will need to present your results in terms of graphs. Be sure your range of input sizes is large enough so you can get a good idea of the asymptotic performance.

• Comparing the two Algorithms: You can compare the running times of your two algorithms using graphs (present them on the same graph).

• Comparing Asymptotic and Experimental Performance: You will need to think of a way to compare the running time of an algorithm with its theoretical, asymptotic, running time. One way to do this is to present the experimental results and a curve representing the theoretical running time on the same graph.

Grading on this assignment will put the greatest weight on the choice of test data and the quality and insightfulness of your discussion of your results. Don't be put off too much if there are some discrepancies between the theoretical results and the experiments. If that happens, try to explain why it occurred.