Course Project

The project can take several forms:

• Solve an open theory problem, formulate a new problem, or make some other contribution to the study of algorithms/lower bounds for processing big data.
• Implementation: (1) implement an algorithm and use it to analyze some dataset in a way that would be hard to do without sketching, (2) design and build a system that uses sketching in a meaningful way, or (3) do an empirical comparison between implementations of various sketching algorithms that solve the same problem.
• 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. Sketching algorithms should somehow be involved though.

Project Proposals:

You must submit a project proposal by Wednesday, October 28, 2020. Submit your proposal via email to sketching-fall20-staff@lists.eecs.berkeley.edu with filename of the form [first-initial][last-name]-project.pdf (e.g. flast-project.pdf for First Last). If there are multiple members on the team, only one submission need be made, and name the file using any of the team members’ names (make sure all members’ names are written in the proposal though!).

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).

Policies:

• You may work in teams of up to three on the project. Each team only needs to submit one project wite-up, and the presentation time will be split evenly between the team members. All team members receive the same grade on the write-up portion of the project. 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, December 11, 2020, 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 body.
• As with problem sets, your paper must be typeset in LaTeX. Submit your paper via email to sketching-fall20-staff@lists.eecs.berkeley.edu with filename of the form [first-initial][last-name]-project.pdf (e.g. flast-project.pdf for First Last). If there are multiple members on the team, only one submission need be made, and name the file using any of the team members’ names (make sure all members’ names are written in the paper though!).
• You are also required to do a presentation during the last few lectures.