Computer Science 429: 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:
-
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. Suggested topics:
suffix trees, suffix array,
linear-time construction for large alphabets, etc.
- Complexity of union-split-find problems. Research some of the extensions explored in that
Master's thesis. Perhaps conduct your own exploration of
some version of the Union-Split-Find problem.
-
Look at Section VII of CLRS (Cormen, Leiserson, Rivest aand Stein, Algorithms. Topics covered there are Sorting Networks, Arithmetic Circuits, Algorithms for Parallel Computers, Matrix Operations, Polynomials the the FFT, String Matching, and Computational Geometry.
Here are some good ways to find topics:
- Prof. Andoni at Columbia lecture resources
- Notes from MIT Advanced Algs 2004Check out Fibonacci Heaps, also covered in CLRS.
- U Wisconsin Scribe notes