The CPSC 501 Essay, Fall 2019
This page concerns the written essay for CPSC 501 Section 101. It is worth 20% of the overall grade.
| Essay Content |
The essay should be survey: you take a topic in Computer Science Theory
(a few research papers, part of a book, a theorem with a very long
proof, etc.) and you should (1) summarize the results, (2) provide
examples, (3) describe part (but not all) of the proofs, (4) identify
currently open problems, (5) etc.
Your summary, examples, choice of which material to present should be your own, original work. Be careful to avoid plagiarism--you have to acknowledge your sources, you cannot copy large passages from any article or book, etc. The typical length of the essay is 7-15 pages (in 12 point LaTeX with standard margins). |
|---|---|
| Audience and Essay Structure |
The essay should be written for a reader familiar with the course textbook
(by Sipser), but nothing more.
You should not repeat anything in Sipser's textbook, but you should define
any concepts beyond Sipser's textbook (and
300-level algorithm and math courses).
The essay should be written similar to a research article: it should begin with an abstract; the first section should be a non-technical introduction (with few or no formulas or technical terms) with a review of the literature; the section section should formally state the main results (and give necessary definitions and terminology). You should have a bibliography at the end that includes all sources that you have used, and closely related sources. |
| Grading | The grading is based largely on (1) the originality of the material, (2) how concise and readable the article is, (3) technical difficulty, (4) correctness and organization of the material, and (5) adequacy of the bibliography. |
| Due Date | The essay is due on November 29 at 11:59pm. |
| Sample Topics | The topic should be in the area of modern Computer Science Theory. Example of topics include: communication complexity, circuit/formula depth/size complexity, complexity in cryptography, explicit constructions (expanders, extractors, etc.), a topic in PAC learning, sparsification of linear systems, linear program algorithms (from the theory view point). |
| UBC CS Home | | | Joel Friedman Home | | | Course Materials |