The CPSC 501 Presentation and Report, Fall 2023

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, and 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.

Your presentation should have: (1) motivation, historical context, and summary; (2) any formal definitions you need and motivating example(s) (HERE you should stop for questions from the class); (3) a brief discussion of some technical details (mostly likely you will have to choose only 1 or 2 representative ideas, methods, etc.); (4) optionally a statement of 1 or 2 future research directions, open problems, etc.; (5) at least one slide of bibliographical references.

You may work in groups of size up to 3; 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. You will have very little time! You'll have to be very selective about what to present.

You should submit a brief report on the topic of your presentation, due on Thursday December 7, 2023 (the last day of classes); the report can have some material that you chose to omit (e.g., technical details, examples) from the presentation. In your report you can correct any mistakes in your slides and presentation.
Audience The 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; 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 understandable it is to the audience; and (4) adequacy of the bibliography.

A common mistake is to present material too quickly, and you may lose points for this. This usually happens when people try to present too much material for the allotted time; the result is often, ironically, that almost no material is actually understood by the audience. Make sure you test your presentation on someone (not in your group) and get some feedback before presenting it to the class.
Due Date 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 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, 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