Solve an open theory problem, formulate a new problem, or make some other
contribution to the study of algorithms/lower bounds for processing big
Implementation: there are a few options here. For example, (1) pick a problem
and implement at least one sophisticated algorithm for the problem (e.g. BNW
for shortest paths), or possibly multiple to compare, trying to find
heuristics that might provide practical speedup, or (2) design and build a
system that uses provably good algorithms such as those learned in class.
Write a survey on a few related papers. A good approach is to first try to
solve an open problem, which generally requires reading several background
papers first, then switching to a survey if the problem evades solution.
You are encouraged to relate the final project to your research interests, and
you will not be limited to the topics discussed in class. Techniques/topics
related to the focus of this class should somehow be involved though.
You must submit a project proposal by Friday, March 24, 2023 to Gradescope.
If there are multiple members on the team, you can each submit the same
PDF to the Gradescope assignment (make sure all members’ names are written
in the proposal).
Whether to approve your project’s theme is based on the proposal, so it
is imperative that you do some serious thinking about the project before
writing the proposal. Even though you should not change the topic of the
project after submitting a proposal, you may change the form of the project
(such as writing a survey if you fail in bringing a theoretical contribution).
You may work in teams of up to three on the project. Each team only needs
to submit one project wite-up, and all team members receive the same project
grade. You are allowed and encouraged to consult with anybody, including
the teaching staff, when working on your project.
You must submit a paper by 11:59pm on Friday, May 5, 2023, which should be
at most 10 pages, excluding title page (which can include team member names,
title, and abstract) and bibliography. Use at least 10pt font and 1 inch
margins all around. A clearly marked appendix of unbounded length can
follow the bibliography, but there is no guarantee that any of it will be
read. As such, keep the most interesting parts of your work in the 10 page
As with problem sets, your paper must be typeset in LaTeX. You will submit
your paper on Gradescope, and team members should each submit the same PDF
(again, making sure all team members’ names are written in the paper).