CS360 Final Project

Due: Monday, May 8th (101) or May 10th (102) 10:15am-12:15pm (final exam period)

Email a .pdf of the final report to dbabcock@ycp.edu by noon on May 11th.

The purpose of this project is to give you a chance to investigate an algorithms topic that we did not cover in class. Section VII of Cormen, et al. contains many good topics including multithreaded (parallel) algorithms, matrix operations, linear programming, FFT (Fast Fourier Transform) computation, cryptography algorithms, string matching, convex hulls, approximate solutions for NP complete problems, etc. You may also choose a relevant topic not covered in the book with instructor approval.

All projects will require a short report along with a very brief presentation. The project may take one of two forms:

1. If there is readily available pseudocode (e.g. book algorithms), the project should consist of an implementation (preferably in C++), benchmarking of the algorithm for various size inputs and comparison with asymptotic analysis of both executable lines and actual clock time, and some research regarding extensions and/or alternate implementations.
2. If there is not readily available pseudocode or it is prohibitively complicated to implement, the project should consist of a detailed description of the operation of the algorithm along with a complete analysis of correctness and asymptotic running time. There should be significant research into the potential applicability and possible extensions of the algorithm.

Written Report

The report should be 5-7 pages in length (double spaced) including figures and appendicies and contain the following sections:

• Abstract - an overview of the topic.
• Introduction - a brief motivation for the topic, i.e. to what problem domains does the algorithm apply (especially real world problems).
• Implementation - an explaination of how the algorithm works along with an argument for the asymptotic running time. You may choose to include a figure with the pseudocode from the book (appropriately cited) to refer to particular lines. You should NOT include proofs (unless they are extremely illustrative) or examples here.
• Results (type (1)) - a figure(s) and corresponding discussion of the benchmark results concerning correlation with the asymptotic behavior as well as rationale for any discrepencies.
• Extensions - a discussion of at least one current reference on the topic (see the end of chapter notes from the textbook or use the web) explaining improvements either via better algorithms or a more efficient implementataion (or possibly that there are none). Note you do not have to implement the improvements, but merely present what is currently the “best” way including caveats, restrictions, constraints, conditions, etc. that are necessary.
• Conclusion - a concise restatement of the motivation for the topic, the algorithm presented, any implementation results, and the curent “state-of-the-art”.
• Works Cited - any referenced sources.
• Appendix - source code, table of benchmark results, and/or a simple example demonstratating the algorithm.

Oral Report

Since we have a large class, the presentations should be no more than 5 minutes. You will not have time for PowerPoint slides, but the presentation should cover:

• The topic with relevant problem domains.
• A very brief discussion of how it works.
• The current “state-of-the-art” that you have found.

Grading

The project will be graded as a total package based in part on the overall difficulty as well as the quality of the report and (to a lesser extent) the presentation. This means that selecting a simple algorithm will require a more extensive discussion of results and improvements and vice versa for more challenging algorithms.