CS41: Final Project

Overview of Requirements

Do not blow off the initial report or checkpoints. The action plan should describe what tasks you plan on accomplishing in the remaining three weeks. Each checkpoint should describe how tasks from the action plan have been accomplished, or what issues have arisen that prevented intermediate tasks from being completed on time.

This final project should be done with one partner*, but you don't have to work with your usual partner. In fact, I recommend looking at possible topics on your own and then finding a student with similar interests. You are welcome and encouraged to discuss ideas with anyone in the class (not just your lab or final project partner).

*Working in a group of three is OK as long as the overall work is roughly 50% more. Mention that you have a group of three in your project proposal, and in your action plan describe the additional goals you plan to achieve with the extra person in your group.

*Working alone is allowed but not encouraged. There is no workload discount for working alone -- your project will be judged as if it was a partnered project.

Frequently Asked Questions

Introduction

Throughout the course, we we have seen several algorithms and structures for organizing and manipulating data and performing computational tasks. With each, you have built the foundations of your computational knowledge base that will aid you as you continue to mature as scientists. The constraints of a 14-week course limited the number of algorithms topics we considered, as well as the variations and nuances of some that we did cover. The central goal of this course, however, was not to memorize every algorithm technique and problem ever considered. Rather, it was to develop the skills of design and analysis that are a prerequisite to becoming a competent computer scientist.

For your final project, you will demonstrate these newly acquired skills by exploring algorithms and data structures at a deeper level than what we've been able to cover in class. You will write a medium-length paper which will discuss your chosen topic. Your report should introduce the topic, provide a motivating example, compare and contrast to a related course data structure, and analyze a few important operations. You will demonstrate not only your conceptual understanding of the topic(s), but also your ability to analyze algorithmic efficiency.

You will be evaluated on your written communication skills, as well as your oral communication if you propose to give a presentation, so be sure to understand the motivation of your topic.

Project Format and Deliverables

The default end deliverable for your final project is an 8-10 page paper. However, to encourage creativity and enable a wider variety of projects, I am flexible as to what the main output will be. Some alternate examples include: Original research will carry some weight but less than you'd get from a directed reading or summer research project. Every project should include a final writeup of some length, and the intermediary requirements described above.

Choosing a Topic

The choice of topic (algorithm, data structure, problem, ...) to consider is largely open-ended. However, you must send a short abstract (one paragraph) explaining your plan by Friday April 3. This should include the topic you plan to cover, what you aim to discuss in your paper, and what else you plan on producing (say C++ code if you plan on implementing an algorithm or data structure). You can use either book (Kleinberg/Tardos or CLRS) to find example algorithmic topics we did not cover, or explore resources online. While Wikipedia is not a primary source, it is a reliable repository of algorithms, data structures, and complexity classes that can be easily explored and there are usually good examples.

Other resources include: Some example algorithm topics include: Some Complexity-related topics include: Some example data structures include:

Writeup Requirements

Your writeup should be well-structured and follow scientific writing principles. You can structure as you see fit, but at a minimum, your paper should include:

Your paper should be typed in LaTeX; no hand-written writeups will be accepted. The exception is with illustrations, which can be neatly drawn and attached to your writeup. I would prefer you scan and attach the images to your PDF document, if possible. If you are interested, feel free to email me any LaTeX questions.

In terms of the length of your writeup, it is really up to you to judge how much material adequately describes your data structure/algorithm. Your writeup, excluding figures, should not exceed 10 pages using 1.5 spacing, 11 point font, and 1 inch margins.

Presentation

A presentation is not required but could be a nice component for a final project. If you choose to do a presentation, it should run 20-30 minutes and will be given in lecture or lab during the final week. Depending on how many groups want to do presentations, all other students will evaluate your presentation on the following criteria:

  1. Rate the introduction/motivation for the material
  2. How effective was the presenters sample illustration in conveying the high-level features of the data structure/algorithm?
  3. Overall, how effective was the presentation in explaining the data structure or algorithm?
  4. Briefly, describe the strongest part of the discussion
  5. Briefly, list one thing the presenter could improve upon to help you understand the topic better
Both partners are expected to contribute equally to the presentation and lab writeup

Presentation Logistics and Tips