The CPSC 501 Essay (and Possible Presentation), Fall 2024

This page concerns the written essay for CPSC 501 Section 101. If time permits, you will be asked to give a brief presentation to the class about your essay. The essay and possible presentation are worth 20% of the overall grade.

Content and Structure The essay should concern a topic related to CPSC 421/501.

You should present one or more articles, part of a book, a difficult theorem, etc., that we haven't covered in CPSC 421/501. The essay should be your own, original work. If time permits, you will also be asked to give a presentation on your essay; if so, you should be prepared to answer brief questions DURING and at the end of your presentation.

Your essay (and presentation) should have: (1) motivation, historical context, and summary; (2) any formal definitions you need and motivating example(s); (3) some technical details (in a presentation you won't have much time, and you'll have to be very selective); (4) optionally a statement of 1 or 2 future research directions, open problems, etc.; and (5) a bibliography.

You may work in groups of size up to 2; your essay should be roughly 1000-3000 words long per group member (please ask me if you'd like more than 3000). If presenting, each group member should speak (including time for questions) for X minutes, where X will depend on the number of CPCS 501 students this year.
Audience Your essay and presentation should be understandable to folks familiar with Chapters 1,3,4,7 of Sipser's textbook and the course prerequisites. Any concepts and terminology beyond this should be explained carefully and well motivated.
Grading The grading is based on: (1) originality; (2) the correctness and organization of the material; (3) how understandable it is (assuming an audience as described above); and (4) adequacy of the bibliography.

If you present your essay, make sure you test your presentation on someone (not in your group) who isn't already familiar with the material in your essay; a common problem in presentations is that the speaker(s) try to go over too much material in the allotted time.
Due Date You should submit your essay by Friday, December 6, 2024 (the last day of classes). If time permits, the presentations will be given for part of the last two weeks of class.
Sample Topics Please check will me before you choose a topic; your group topic should be different than those of other groups.
Here are sample topics (there are many other possibilities):
  • Topics from Sipser's textbook that we will not have time to cover, including: Kolmogorov-Chaitin complexity (Section 6.4); one proof of a Godel incompleteness theorem (Theorem 6.16; the key is to give more details about why Lemma 6.14 is true; beware that Sisper's textbook omits the fact that a "formal proof" depends on the axioms you provide);
  • the theorem of Hennie that there are languages recognizable in linear time on a 2-tape machine that cannot be recognized by a 1-tape Turing machine in time o(n^2) (see "One-Tape, Off-Line Turing Machine Computations," Information and Control, 8, 553-578 (1965));
  • how to build a "Godel sentence," giving an explicit example of a true but unprovable (in the given proof system) statement, provided that the system is consistent.
  • communication complexity and its relationship to circuit/formula depth;
  • lower bounds in circuit/formula depth/size of Boolean or algebraic functions;
  • explicit constructions (expanders, extractors, etc.) for combinatorial devices used in algorithms;
  • a topic in PAC learning,
  • linear program algorithms (from the theory view point);
  • an applied aspect of parsing context-free grammars (CFG's are introduced in Chapter 2 of the textbook, but not much is said about how to parse such languages in practice);
  • machine learning of automata (e.g., courtesy of Prof. Frank Wood, some years ago, this CACM 2011 paper, this NeurIPS 2011 paper, and this paper on infinite state PNFA's and PDFA's);
  • practical aspects of running DFA's and NFA's.

UBC CS Home| Joel Friedman Home| Course Materials