UW Logo

CS 666, Fall 2022

Project Guidelines

(link to CS466/666 home page)

There are two projects: One means reading a paper superficially, one means reading it in more details.

Abstract-project (5%):

Due Oct 7, 5pm. Short version: Pick a course-relevant paper and critique its writing-style.

Longer version:

  1. Pick a paper that is relevant to course content and relatively recent (publication year 2010 or later).
  2. List the full citation of the paper as well as a DOI. (Hint: dblp.org gives you complete information, and also BiBTeX entries.)
  3. Write a short summary of the paper (2-3 sentences). Do not copy the abstract verbatim.
  4. Say how the paper relates to course content (2-3 sentences).
  5. Read pp. 1-4 of the writing-guide by Knuth, Larrabee and Roberts https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf, i.e., points 1-23.
    (You are strongly encouraged to read more than this!)
  6. Find three of these points that are violated in the paper that you summarized.
  7. For each of these three points, state what the original paper said, why this is a violation to which point, and how you would rewrite the sentence(s) to fix it.
Submit a LaTeX-file to LEARN.

Some comments:

Presentation-project (15%):

Due Dec 5, 5pm. Short version: Pick a course-relevant paper, and create a presentation of it.

Long version:

  1. Pick a paper that is relevant to course content and relatively recent (publication year 2010 or later). Possible papers from the abstract-project will be posted below (and perhaps some others as well). You are permitted (in fact, encouraged) to pick a paper relevant to your own research interests.
  2. Read the paper superficially. Select material from the paper (and/or related papers) that would fill approximately half a lecture of cs466.
  3. Read in-depth the selected parts of the paper(s) and understand every step of it. (If some parts are truly incomprehensible, seek help early!)
  4. Create slides to present the selected parts of the paper(s). These should ideally include the entire proof, but if that's too long, they should focus on the hardest of the cases. The slides should be identical to the ones used during the presentation.
  5. Give a half-lecture presentation about the paper. This can either be done by video or in-person (by appointment, likely on Dec 6). Expected length is 30-45 minutes.
  6. Answer questions that I have about the paper and your presentation. This will be done during the presentation (if done in-person), and with a separate appointment (likely on Dec 7) if creating a video.
Upload the slides as PDF to LEARN. If using a video, send me an email with a link to a place from where I can download it (preferably within the vault).

Some comments:

Possible presentation-topics:

Below is a list of suggested problems/papers. You are encouraged to look for other problems on your own, but double-check with the instructor whether your topic is appropriate. Projects will be marked if they have been "taken". This list will be added-to during the term.

On finding research papers

To get a feel for recent research in algorithms and complexity, browse through conference proceedings such as FOCS (IEEE Sympos. on Foundations of Computer Science), STOC (ACM Sympos. on Theory of Computing), and SODA (ACM-SIAM Sympos. on Discrete Algorithms). Final versions of proceedings versions are often published as journal-papers (and then usually longer and better-explained); you may want to check DBLP for the author(s) or title.
Another avenue is to find known papers (e.g. from class) on CiteSeer or Google Scholar, and then to investigate newer papers that cite them (hence presumably cover similar topics).