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:
What does the algorithm do? I.e., what problem does it solve?
Who created the algorithm(s)? I.e., give a history of the work on the problem.
What algorithm did you implement? Why choose that one?
How does the algorithm work?
Why is it considered correct?
What is the run time analysis?
What other algorithms do the same job -- how does this algorithm fit into the landscape?
Here are some potential topics:
Here are some good ways to find topics:
Theoretical Stack Exchange problem 45524
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.
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.
- Prof. Andoni at Columbia lecture resources
- Notes from MIT Advanced Algs 2004Check out Fibonacci Heaps, also covered in CLRS.
- U Wisconsin Scribe notes