CS/SE 7301.003.20S — Course Projects

A large portion of your grade will come from a semester project. Projects may be submitted by teams of up to two students, although three students may be allowed to do a common project after justifying it to Kyle first. Students may collaborate outside of their teams, with anyone in or out of class (with proper credit). At the end of the semester, each team will submit a written document of around 10 pages and give a short presentation of around 20 minutes. Project reports are due Wednesday, November 25th. They should be submitted by at least one student per group on eLearning as pdfs.

Project types

Projects can take on any number of forms:

Theoretical: Attempt to solve an interesting, non-trivial, and preferably open theoretical problem related to computational topology.
Experimental: Implement and experimentally evaluate a few algorithms or data structures for one or more closely related problems in computational topology. Projects of this type will preferably compare algorithms or data structures that have known theoretical guarantees versus those used in practice in cases where they differ.
Scholarly: Write a comprehensive survey on a topic relevant to computational topology. Surveys should be a bit longer than theoretical or experimental reports, and they should include a history of the topic; a description of motivating applications; a summary of known results; sketches of the most important algorithms, data structures, and/or proofs; suggestions for future research; and a thorough bibliography.
Creative: Do something else cool and relevant to computational topology.

You are strongly encouraged to work on projects motivated by your primary professional development or research interests. Project topics need not be limited to specific topics in class, as long as they focus on computational topology. You should work on or study problems whose solutions you want to know but don't.

Project proposals

Project proposals are due Friday, October 23rd. They should be submitted by individual students on eLearning as pdfs. Proposals should be one to two pages in length, and they should include a crisp self-contained statement of the proposed topic, a brief survey of known results, a potential plan of attack, and, if theoretical, one or two half-baked ideas that probably won't work but hey you might get lucky. After everything is submitted, we will post submitted proposals to eLearning and/or MS Teams as inspiration for final projects. However, final projects need not focus on any of the proposed topics. If you have a good idea of what you want to do for your final project, feel free to work on it before project proposals are due.

The goal

The ideal result of the project is the creation of a concrete product or knowledge that can be used in your future career or perhaps a publishable paper. It's understood, especially if you try for a theoretical project, that you may not find a complete solution or answer all your questions. Whatever the result, your writeup and presentation should describe partial results, promising approaches for ongoing work, remaining questions you would like answered, and ideas that initially looked promising but weren't (and why).

Past projects

To provide some inspiration for your own projects, here is an incomplete list of projects done in a a computational geometry class Kyle taught in Spring 2018.

A survey on probabilistic road maps for motion planning
A survey on algorithms for computing shortest paths in motion planning
Theoretical research on quickly approximating the diameter of a point set
Implementing geometric algorithms for problems such as collision detection as part of a mixed reality mobile application
Theoretical research on the expected computational complexity of Voronoi diagrams where sites can only "see" points in a halfplane and cells are determined by closest site seeing each point
Experimental evaluation of using different curve similarity algorithms to perform handwriting recognition
Implementing geometric algorithms for a face morphing/blending application
Theoretical research on problems involving separating red and blue sets of points
Survey on ray and arc shooting data structures
Survey on computing geometric spanners relevant to wireless ad hoc networks

The main ideas behind the project format and large amounts of the language here are due to Jeff Erickson. This page includes a number of good suggestions on where to find good problems both for this class and in the future.