COMP 150 Projects
Spring 2017 COMP 150
Three surviving COMP 260 projects from Spring'14
Link prediction, by Ahmad Sadraei.
Tries, by Alex Schultz.
Lossless data compression with suffix trees, by Jerry Huang.
Max Goldstein's independent (i.e., just for fun) projects on Melkman's algorithm
and intro to Linear Algebra.
What should your project involve?
- You can implement an algorithm. In this case you should discuss any choices you made and difficulties that you encountered. Always acknowledge parts of code or ideas that you found elsewhere. If you decide to implement, you should also run some experiments, and provide a report.
- You can create a visual demo of an algorithm or proof. In this case you don't need to actually implement the algorithm. It is possible to show the user what the algorithm does, while some brute-force version is running in the background. For example, if during a particular step of some algorithm you say "now we find the median" and you illustrate the median of a set of elements, your code could just have sorted instead of using median-finding.
Your demo should have lots of images and animations, examples, color, etc. Basically anything that would make the user want to find out about a topic through your demo rather than reading other available sources. Your demo should be easily accessible to everyone. Downloading some package is less attractive than a demo that can start with one click online.
Ideally your demo will be interactive. This means that the user will be able to enter input or try out multiple examples.
You can describe an algorithm, proof, or general topic in great detail, without all the demo advantages... as long as you go way deeper into non-trivial theoretical results. Don't pick a topic that is already easy to find online or in standard textbooks.
- I am open to other suggestions.
Project deadlines (for Fall 2017 term)
- By October 5: provide three brief project proposals. Each should have a title and a brief description of the topic. These will be shared with the rest of the class.
- By October 20: select your topic and describe what you plan on doing in more detail.
- By November 5: provide a website with an outline of your project. If you are doing an interactive demo, you need to show that you are able to process user input by this date.
- By November 28: have a reasonable draft of your project, and enough done to be able to give a presentation about your completed or ongoing work.
- You may work on your project until the end of December, but I expect a complete project by December 15, after which only minor revisions should be necessary. I advise you to get this done much earlier so that you're not surprised by how many major revisions I might require.
How do you pick a project?
- Browse the course contents. There are several suggestions listed. Also if you find a topic interesting, a simple web search will often reveal extensions and recent research.
- Look at old projects and ask me if they can be extended (or in some cases, redone).
- Scan through conference and journal proceedings: Find some research paper that looks interesting.
Conference and journal proceedingsNote that selecting a paper from a prestigious conference will be impressive but you might also get stuck on details and have to dig much deeper to understand what is being described. Chances are that it will not be self-contained. The smaller conferences contain many papers with interesting results that are non-trivial while still at a level that is accessible to students. They often also have suggestions for further research.
You may need to access some of the following via your university portal.
- There is a wiki list of CS conferences. A few are highlighted below.
- SODA (Symposium on Discrete Algorithms) [very prestigious, high level]
- ESA (European Symposium on Algorithms) [a notch below SODA]
- GD (International Symposium on Graph Drawing)
- ISAAC (International Symposiums on Algorithms and Computation)
- WADS (Algorithms and Data Structures Symposium) [formerly Workshop on Data Structures]
- SWAT (Scandinavian Workshop on Algorithm Theory)
- LATIN (Latin American Theoretical INformatics)
- SoCG (Symposium on Computational Geometry) [very prestigious, top level for the field]
- CCCG (Canadian Conference on Computational Geometry) [an international conference, good for projects. Open access]
- EuroCG (European Conference on Computational Geometry) [an international conference, good for projects]
- FWCG (Fall Workshop on Computational Geometry) [U.S.-based. 2-page results, the most informal of this list]
- JACM (Journal of the ACM)
- SICOMP (SIAM Journal on Computing)
- IPL (Information Processing Letters) [relatively short results]
- DCG (Discrete & Computational Geometry) [top level for the field]
- JoCG (Journal of Computational Geometry) [relatively new journal, meant to be SoCG level, open access]
- CGTA (Computational Geometry: Theory & Applications) [good papers, but not necessarily DCG level]
- IJCGA (International Journal on Computational Geometry and Applications)