Computer Science 429: Projects

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 teaching the class an algorithmic topic, or you can undertake original algorithms research/exploration. Either can include coding up an algorithm, and you are permitted to use AI to help generate code, and you can incorporate freely available code written by others if allowed under the originator's copyright; in either instance, you must provide references, including a description of attributed material. Note, however, that not much of the grade for the course can be associated with the software solution provided; in exceptional circumstances, if you have developed an original coded solution, more of the grade can be on the software you produce -- you must negotiate that with the instructor in advance (i.e., when you know the significant portion of your effort will be dedicated to that work). You will be graded on your achievements. 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.

Due Nov 18 The project description is a two-pager that outlines what you propose to explore, and should answer the following questions:
  1. What is the algorithmic problem?
    E.g. Problem: Dynamic Spanning Trees: We want efficient online algorithms that maintain information about a minimum spanning tree in a graph, given that the graph information is subject to updates of the form "modify the edge (u,v) to have weight w" where w can have any real value or ∞, which is equivalent to removing the edge.
  2. Identify (if relevant) a naive method and analyze its running time.
  3. Identify the paper(s) you are studying that give a better solution to the problem.
  4. Give background on work done to come to better algorithms; provide running times or other related metrics (like approximation ratios, if studying an approximation algorithm).
  5. Introduce the algorithm you are studying. Explain the algorithm, give it in pseudocode, and show how it works on small examples. Provide an analysis of the algorithm. If you have it coded, give practical run-times on data sets of various sizes.

Due Dec 5 4:00 The project paper should cover the following:
  1. What does the algorithm do? I.e., what problem does it solve?
  2. What other algorithms do the same job -- how does this algorithm fit into the landscape? Give background on work done to come to better algorithms; provide running times or other related metrics (like approximation ratios, if studying an approximation algorithm).
  3. How does the algorithm work? Introduce the algorithm you are studying. Explain the algorithm, give it in pseudocode, and show how it works on small examples. Provide an analysis of the algorithm. If you have it coded, give practical run-times on data sets of various sizes.
  4. Why is it considered correct?
  5. What is the run time analysis?


Here are some potential topics:
  1. Theoretical Stack Exchange problem 45524. If you want to get started here, do a search on David Eppstein, who posts with insight on many problems. An example: "Edit distance in Sublinear Space".
  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. We will be taking in class 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. Related problems to that might be good topics. Erik has ma
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