One-Dimensional Computational Topology

CS 598 JGE, Fall 2017

Main    Schedule    Homework    Projects    References

A majority of the grade in this course is a two-part final project. The basic requirements of the project are quite open-ended:

The precise form of the project is also open-ended; here are a few possibilities:

Students are strongly encouraged to work on projects motivated by their primary research/development interests and to collaborate outside their teams, with anyone in or out of class (with proper credit, of course). In particular, project topics need not be limited to the specific topics covered in class, as long as they relate to both algorithms and embedded curves and/or graphs. Especially for theoretical projects, you should work on problems whose solution you want to know but don't.

The ideal final outcome of the project is a publishable result. Any student who publishes work from this class in a peer-reviewed conference or journal will automatically get an A+. This rule can be (and has been!) applied retroactively for several years after the course ends.

However, it is not reasonable to expect to obtain publishable results on any problem after only one or two months of effort, especially in a new area. Thus, most final reports will describe the team's incomplete progress toward a solution. This progress can take several forms: a thorough literature survey, a complete solution for some interesting special case or necessary lemma, a plausible plan of attack, counterexamples that killed a seemingly plausible plan of attack, conjectures backed by experimental evidence, interesting approaches that didn't pan out, ideas that seemed smart at first but turned out to be stupid, and so on. You know, research. Creative failure is better than straightforward success. Yes, really.

But how do we find good problems?

Excellent question! Here are a few hopefully useful suggestions. This list is nowhere near exhaustive, nor will every suggestion work equally well (or at all) for everybody. If you have other ideas for finding good research problems, I'd love to hear them!


Creative Commons License   Powered by MathJax