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:

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:

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.