Computer Science 385
Design and Analysis of Algorithms

Spring 2019, Siena College

Home     Syllabus     Schedule

There is an exciting event taking place at Siena for the first time this semester: an all-day Academic Showcase on Friday, April 26, 2019. Classes are cancelled for that day, and instead everyone will participate in a variety of talks, poster sessions, demonstrations, and other events sharing and celebrating your academic achievements and those of your fellow students and the faculty. Plan to be on campus the whole day.

There will be a session dedicated to our course 2:30-3:30 PM in Roger Bacon 340. Everyone is required to attend and participate in our session, which will be open to the campus community. The goal of this project is to learn about a few algorithms, implement them, apply them to some interesting data, and share what you learn at the Academic Showcase.

This project is worth 150 points in the problem sets category.

As this is the first Academic Showcase, it's also the first time an Algorithms class is participating in it, so watch this page and listen in class for updates, clarifications, and other news related to this project.

Group Formation and Repositories

Everyone is strongly encouraged, but not required, to form groups for this project. Groups of 3 should work well, but requests to form larger groups will be considered in cases where the work proposed is sufficient to justify a larger team. Groups must be formed by 4:00 PM, Monday, March 18, 2019 by an email to jteresco AT siena.edu with the names and GitHub ids of all team members. You will receive a reply with the link to follow to set up your GitHub repository. Only one member of the group should follow the link to set up the repository on GitHub, then others will be granted write access.

Project Requirements

The goal of this project is to study, implement, and analyze algorithms beyond what we have time to discuss in class, labs, and problem sets. Here are the guidelines:

• Each project will consider two or more algorithms. These algorithms should be applied to some interesting data.
• Algorithms could be ones we do not study at all in class, or could be applications of algorithms that we do study to solve some problem of interest.
• An algorithm might not be one you'd readily find in a textbook but instead be a variation on an algorithm or algorithm design technique applied to a specific problem.
• All projects must make some use of METAL graph data in some way with at least one of the algorithms studied. There is additional data from the Travel Mapping project that can help make things more interesting. Travel Mapping has information about individual roads and highway systems, as well as user information about what roads they have traveled.
• Especially ambitious teams could develop enhancements to the Highway Data Examiner algorithm visualization tool. New features could be added to existing algorithm visualizations or new algorithm visualizations could be implemented within the system.
• In order to have a variety of algorithms represented across all of our projects, a specific application of any specific algorithm may only be done by a small number ( <= 3) of teams. Claim your intended topics as soon as you have ideas by email or in person.
• All sources used must be cited properly.

Deliverables

The project requies a series of deliverables over the last several weeks of the semester.

Proposal

The first deliverable is a written proposal, due at 4:00 PM, Monday, March 25, 2019. This should be done by creating a file in your GitHub repository. The preferred mechanism is a document proposal.md in GitHub markdown, but you are also permitted to commit and push a PDF document proposal.pdf to your repository. You are encouraged to discuss your ideas right away. Your proposal, at most one page in length, should describe your proposed project, what specifically you plan to investigate and implement, and how you plan to go about it. Describe the major milestones for your project, a rough schedule for achieving these milestones, and which milestones you believe are most important for your project to be considered a success. If you will need access to any special hardware or software, include that in your proposal. Your proposal should convince me that you have an interesting, worthwhile, and relevant topic and that it is feasible in the time available.

The proposal is worth 20 points.

Progress Report

By 4:00 PM, Monday, April 8, 2019, submit a progress report. This may again be a GitHub markdown file progress.md or a PDF document progress.pdf committed and pushed to your repository. This should outline your progress to date, indicate any changes to your plans since the proposal, and include a more specific timetable for completion of the project.

The progress report is worth 20 points.

Academic Showcase Presentations

Everyone is required to take part in the presentation of their group's work at the Academic Showcase 2:30-3:30 PM on Friday, April 26, 2019. Each group will set up at one or two tables in Roger Bacon 340 and be available to demonstrate and discuss your work. You could prepare a small poster, but a few slides you can bring up on a computer along with live demonstrations, if applicable, would be appropriate as well. Your presentation needs to work well for two audiences: those with a good understanding of algorithms (your classmates, other upper-level Computer Science students, faculty), and others who might be in attendance with very limited exposure to algorithms. Your task is to teach those in attendance a little bit about the algorithms you have studied and why they are interesting to you, and possibly, to them.

The Academic Showcase presentation is worth 30 points.

Final Submission

By 4:00 PM, Monday, April 29, 2019, all projects materials must be submitted by commiting and pushing to your GitHub repository. The submission should include all of your code, presentation materials, a writeup of your findings (again, either as a GitHub markdown document final.md or a PDF document final.pdf), and any supporting materials such as data sets, empirical analysis results, solutions obtained, etc. Typical writeups would be 10-30 pages in length, including figures and citations, but shorter or longer writeups might be appropriate in some cases.

Your final submission is worth the remaining 80 points.