Computer Science 422: Possible Project Topics

To pass the course, you will need to research an algorithms topic, write up your research, and present the results to the class.

You can choose to emphasize coding a solution, or you can do algorithms research, wherein you undertake original algorithms research. The balance of how much code and how much theory is your choice. You will be graded on your acheivements. If the scope is too small but all correct, you may not get as good a mark as if the scope was more ambitious with partial success painstakingly reported and analyzed. On the other hand, more students make the mistake of aiming to widely. In algorithms research, it is fine to start with a problem and as you run into roadblocks you refine your problem down to a case you can actually solve.

The project paper should cover the following:
  1. What does the algorithm do? I.e., what problem does it solve?
  2. Who created the algorithm(s)? I.e., give a history of the work on the problem.
  3. What algorithm did you implement? Why choose that one?
  4. How does the algorithm work?
  5. Why is it considered correct?
  6. What is the run time analysis?
  7. What other algorithms do the same job -- how does this algorithm fit into the landscape?

Here are some potential topics:
  1. Theoretical Stack Exchange problem 45524
  2. Network Flow - push/relabel algorithms Starting at Lecture 6 of these scribe notes from Cornell, from the lectures of David P. Williamson, there is a nice description of an alternative to the augmenting path algorithm we studied in class.
  3. Erik Demaine's Lectures. I particularly like the topics in L15 and L16, least common ancester and range-minima queries, and suffix tree, suffix array, linear-time construction for large alphabets, etc.
Here are some good ways to find topics:
  1. Prof. Andoni at Columbia lecture resources
  2. Notes from MIT Advanced Algs 2004Check out Fibonacci Heaps, also covered in CLRS.
  3. U Wisconsin Scribe notes