CS 684 Final Paper

Bart Massey

Here's a few brief notes and instructions on the CS 684 Final Paper. This paper is required of Ph.D. students registered for CS 684. For students registered for CS 584, it may be submitted as an (unspecified) extra credit project.

Topic

The Final Paper should cover an interesting algorithm, either:

• An algorithm from the literature.
• An algorithm you or a close associate have created yourself.

The algorithm should be "interesting" in the sense that it is not from the textbook, and not one normally found in introductory textbooks. Ideally, it will be an algorithm with an obvious use case or with interesting theoretical properties.

If you have concerns about your proposed topic, please contact me.

Content

The paper should describe:

• The algorithm itself, including pseudocode.
• What the application or interest of the algorithm is.
• Closely related work from the literature (not in excessive detail).
• Efficiency / complexity of the algorithm, including a worst-case and/or expected-case asymptotic analysis if at all possible. You may include an implementation and benchmark it; this is a good way to understand the difference between theoretical and actual performance.

Format

This is not supposed to be a dissertation. The expected length is 3-6 pages. Please use LaTeX, or provide a PDF from some authoring system that looks as good as the LaTeX would have. Note that the default LaTeX "article" format is kind of weird; you may choose to use something with smaller margins and larger type.

Evaluation

Final Papers are due Friday of Finals Week by 5PM. I will grade them personally. I expect to give full marks to most papers; please make that easy for me.