The CPSC 501 Presentation, Fall 2021

This page concerns the written essay for CPSC 501 Section 101. It is worth 20% of the overall grade.

Presentation Content and Structure The presentation should concern Computer Science Theory or a related area (there are many possible related applications).
You should present one or more articles, part of a book, a difficult theorem, etc. Your summary, examples, choice of which material to present should be your own, original work. You should be prepared to answer brief questions DURING and at the end of your presentation.

You presentation should have four parts: (1) a summary of the content (definitions needed, motivation, results, theorems, open problems, etc.); (2) a presentation of some (but probably not all) details and examples to give the listener some idea of techniques involved; (3) a list of references at the end of the presentation; and (4) time for addition brief questions from the class.

You may work in groups of size up to 4; each group member should speak (including time for questions) for some 10-15 minutes. This is very little time! You'll have to be very selective about what to present.

You will give your presentation via Zoom; please test your presentation on someone else before you give it, to minimize possible technicological problems during your presentation.

You will be asked for a copy of your slides or notes for presentation after you finish (you can correct minor errors after your presentation).
Audience The presentation should be understandable to folks familiar of 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; expect questions on any new terminology.
Grading The grading is based on (1) the originality of your presentation, especially the choice of examples and which details to present; (2) the correctness and organization of the material; (3) how understable it is to the audience; and (4) adequacy of the bibliography.
Due Date The presentations will be done in 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 Siper'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, 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