Class project guidelines, CSE 202

The class project should involve reading, summarizing, analyzing, and critiquing on one or more current research paper (say, under 15 years old) giving an application of algorithms. Generally speaking, a one-person project involves one research paper; a multi-person project should compare two or more related research papers. An exception can be made if a single paper is long or difficult. I would suggest 5 pages as a bare minimum, with say an additional 2 pages per person in the group, but there are no strict length limits. The project must have the following elements:
  1. An application where algorithms are important, and where proposed algorithms are non-trivial .
  2. A discussion of the application and associated constraints on algorithms.
  3. A formal statement of (at least one) algorithmic problem to be solved. Be sure to distinguish between the problem specification and the algorithmic model. Don't confuse constraints/costs for the ALGORITHM (e.g, ``Must be on-line'') with constraints on /costs of the SOLUTION (e.g., ``Must minimize the number of cache misses'').
  4. A clear presentation of at least one algorithm.
  5. A time analysis or other cost (parallel time, memory, distributed time, stability) analysis as appropriate. If the time analysis is not clear, give the best upper bound you can. Think about using data structures to improve the time over naive implementations. Give as detailed a time analysis as possible, in as many parameters as are relevant. (O(nm) is more revealing than $O(n^3)$.) and avoid treating parameters as ``constants'' just because they are fixed in standards. If nothing is proven about the algorithm's time, this might be a place to try experiments with implementations.
  6. A correctness discussion/ proof for at least one algorithm. Prove correctness if correctness is true and known. Otherwise, give examples where the algorithm is incorrect or not optimal. Discuss the approximation ratio for the algorithm. How far off from optimal can the algorithm be? What is guaranteed about the algorithm's performance? If nothing is proven about the algorithm's performance, this might be a place to try experiments with implementations.
  7. A discussion of how well the algorithms presented fit the application. A critique of assumptions made by the algorithm designers. A comparison of alternative algorithm approaches for the application. This can also involve implementation and experiment, or just comparing the analyses but with realistic parameters taken from ``real-world'' instances.