CPSC 421/501 Page, Fall 2020

This page concerns CPSC 421 Section 101 and CPSC 501 Section 101. The courses have been combined, except that CPSC 501 students have an additional presentation to give during the last two weeks of classes.

The class this term will be given FULLY ONLINE.

This page has the most up-to-date information on the course(s) and supersedes any other document.

Materials below may have errors! Errors will be corrected either here or in class. If you are not attending my classes: use these materials at your own risk!

News The final exam on Thursday will be given in two parts as follows:
  • Part 1: 60 minutes, plus 7 minutes to upload Part 1 to Gradescope.
  • Break: 10 minutes.
  • Part 2: 70 minutes, plus 7 minutes to upload Part 2 to Gradescope.
You will be asked to login via Zoom and to keep your cameras on at all times except during the break.

We have added three office hours on the day before the final, in addition to the usual weekly office hours:
  • Monday, December 14, 5:30-6:30pm (Joel);
  • Tuesday, December 15, 3-4pm (Amir);
  • Wednesday, December 16: 11am-12:30pm (Amir), 3-4pm (Adam), 5:30-7:00pm (Joel);
  • Thursday, December 17: no office hours; the final begins at 7pm.

The course Canvas page is available on UBC's Canvas system.
Final Exam Our final exam will be held on Thursday, December 17, at 7pm (pacific time); you must take the final exam at this time. Similarly to the midterm, the final exam is open book, meaning you can use the textbook, the material on our course webpage (handouts and homework and solutions), and any number of printed note sheets. You cannot use any other sources, online or otherwise, including other books.
Here is a study guide for the final exam (last revised Dec 11, 7:20pm).
Breakout Room Problems As per class survey, as of September 29 we will use breakout rooms only on Thursdays.
Some of these problems will be suggested for breakout room discussion; you might want to think about and discuss others outside of class. Some problems involve terms like "convince yourself," which is not a precise homework/exam type problem.
No more breakout rooms!
Older Breakout room problems (these problems also appear in the Board Scans section below):
09_17, 09_22, 09_24, 09_29, 10_01. 10_08. 10_15. 10_22. 10_29. 11_12. 11_19.
Overview This is an introductory course to Computer Science Theory. This policy webpage describes the course policy, including the prerequisites and grading scheme.
To get an idea of the course material and exams, you can look at the CPSC 421/501 from fall 2019; the material covered and the exams will likely be a bit different.
Fully Online This term (September to December, 2020), the course will be fully online. Classes will consist of lectures and some problem solving sessions. We will use UBC's Canvas system to communicate, sign into Zoom and or Collaborate Ultra, and to access recordings of lectures.
All lectures will be recorded (barring technological problems) and will be available via Canvas.
Board scans of all lectures will be posted below.
All material covered in class can be found in the references below.
References The required course textbook is "Theory of Computation," by Michael Sipser, 3rd Edition; all homework from the textbook is based on the 3rd edition. Tentatively we will cover most of Chapters 1, 3-5, and 7, and part of Chapters 8 and 9.

Aside from the textbook, we will use the following articles, which may be revised:
  • Self-Referencing, Uncountability and Uncomputability in CPSC 421; last revised September 3, 2020.
  • This article on the Myhill-Nerode theorem; last revised September 3, 2020. (We will use the Myhill-Nerode theorem instead of the Pumping Lemma in Section 1.4 of the textbook.)
  • This introduction to circuit complexity, (last revised 1:03pm on Nov 26) which summarizes the first part of Section 9.3 of [Sip] and explains some broader context.
    • Midterm Here are the midterm of 9:30am, the midterm of 8:30pm, and solutions to both.
    The midterm is open book, meaning you can use the textbook, the material on our course webpage (handouts and homework and solutions), and any number of printed note sheets. You cannot use any other sources, online or otherwise, including other books.
    The midterm will be delivered to you via Canvas. I have sent out a test message via Canvas (at 8:21am, November 3, 2020).
    The midterm will be held during class hours on Thursday, November 5, 2020. If you are unable to attend class due to your local time zone, you can take an alternate midterm at 8:30-9:50pm on Thursday, November 5; if so, you will need to enter your local time zone on Canvas in September. [It will cover material introduced up to Thursday, October 22.]
    Readings and Boards Scans The following is the rough class plan and corresponding readings; it may be modified.
    • Roughly 2 weeks: Course policy and Self-Referencing, Uncountability and Uncomputability in CPSC 421; this includes parts of Chapter 0 and Section 4.2 of [Sip].
      Board scans: 09_10 (policy, alphabets and strings). 09_15 (languages, set theory terminology). 09_17 (countability, Cantor's theorem). 09_22 (set theory subtleties, Russell's paradox).
    • Roughly 2 weeks: Chapter 1 of [Sip] (Regular languages); we will replace the Pumping Lemma in Section 1.4 with this article on the Myhill-Nerode theorem. In Section 1.3 we will not cover the algorithm to convert a DFA to a regular expression; we do explain that (1) it is not as often needed in practice as the reverse algorithm, and (2) it yields very large expressions for small DFA's like a DFA for the language {0,3,6,9,12,...}.
      Board scans: 09_24 (finish paradoxes, start DFA's). 09_29 (DFA's, concatenate and star, start NFA's). 10_01 (finish NFA's and NFA's in practice, i.e., breakout problem 3). 10_06 (regular expressions and the Myhill-Nerode theorem); on 10_06 we also referred to the the regular expression for {0,3,6,9,12,...} (from the 2019 section). 10_08 (nonregular languages).
    • Roughly 1.5 Weeks: Chapter 3 of [Sip] (Turing Machines).
      Board scans: 10_13 (Section 3.1: Turning machines). 10_15 (Section 3.1: recognizing and deciding; Section 3.2: multitape TMs). 10_20 (Section 3.2: multitape converted to 1-tape algorithm. Section 3.3: descriptions: of graphs, of formulas, etc., as finite strings.) Part of 10_22 (Section 3.3, descriptions of Turing machines)
    • Roughly 0.5 Weeks: Chapter 4 of [Sip] (Universal Turing machines, undecidable and unrecognizable problems). Part of 10_22 (Section 4.2: A_TM is undecidable, universal Turing machines). 10_27 (Logistics regarding CPSC 501 presentations, some logistics regarding midterm, end of Chapter 4.)
    • Roughly 2 weeks Chapter 7 [Sip] (P and NP, the Cook-Levin Theorem, NP-completeness). 10_29 (logistics--midterm and presentations--and P and NP). 11_03 (midterm review). 11_10 (more on NP, start of Cook-Levin theorem). 11_12 (end of Cook-Levin Theorem, with a lot of Boolean algebra). 11_17 (definition of NP-complete, SUBSET-SUM). 11_19 (more NP-complete problems, e.g., CLIQUE, PARTITION).
    • Roughly 0.5 Weeks: Section 9.3 of [Sip], until Theorem 9.20: Circuit complexity, i.e., how some people are trying to solve P versus NP. 11_24 (the above topics).
    • Roughly 1.5 Weeks: CPSC 501 Presentations and Review for Final Exam. Presentations:
      • Nov 24: The Pumping Lemma.
      • Nov 26: Building a Godel Sentence; Kolmogorov Complexity; The Sequence Memorizer (CACM 2011 paper).
      • Dec 1: PAC in Machine Learning; Parsing CF Grammars; Probabilistic Automata and Stochastic Languages.
      • Dec 3: Probabilistic Deterministic Infinite Automata; Neural Turing Machines; a bit of Final 2017 discussion 12_03.
    Homework Homework will be assigned most weeks. We may grade only some of the problems on the homework. Late homework will not be accepted; however, your three lowest scores will be dropped in the overall homework computation.
    All homework involving Sipser's textbook is based on the 3rd edition of this book.
    You should connect to the course Gradescope page via UBC Canvas.
    Individual Homework 1 and Group Homework 1 are due on gradescope.com at 11:59pm Wednesday, September 23. Solutions.
    Individual Homework 2 and Group Homework 2 are due on gradescope.com at 11:59pm Wednesday, September 30. Solutions.
    Individual Homework 3 and Group Homework 3 are due on gradescope.com at 11:59pm Wednesday, October 7. Solutions.
    Individual Homework 4 (corrected on Oct 12: 2(a): 51, not 50 states) and Group Homework 4 are due on gradescope.com at 11:59pm Wednesday, October 14. Solutions.
    Individual Homework 5 and Group Homework 5 are due on gradescope.com at 11:59pm Wednesday, October 21. Solutions.
    Group Homework 6 is due on gradescope.com at 11:59pm Wednesday, October 28. Solutions. For individual practice (not to be handed in), do the 2019 midterm (here are solutions to this midterm).
    Here are some addition practice midterm questions.
    Solutions will not be provided, but will be discussed during class on Tuesday, November 3.
    Individual Homework 7 and Group Homework 7 are due on gradescope.com at 11:59pm Wednesday, November 18. Solutions.
    Group Homework 8 (there is no individual homework this week) is due on gradescope.com at 11:59pm Wednesday, November 25. Solutions.
    Homework 8 is the last homework to be handed in.
    Piazza and Office Hours There will be an online discussion of this course on www.piazza.com; use this link to sign up (for both CPSC 421 and 501). Please post all questions related to the course material to our piazza site. In person office hours (staring Sept 21) can be reached via Canvas, and are currently:
    Joel (Instructor): Monday, 5:30-6:30pm.
    Amir (TA): Tuesday, 3-4pm.
    Adam (TA): Wedesnday, 3-4pm.
    Diversity and Equity UBC is trying in earnest to encourage diversity and alleviate biases and inequities to which some members of its community are subjected; this includes, for example, UBC's Indian Residential School History and Dialogue Center, and well as the Computer Science Department's various programs described on its Diversity in CS webpage. I try to act reasonably free of bias; for example, I do not view sexual orientation or gender as set in stone from birth or as classified by some fixed, finite set of choices; I try to use language accordingly. I will undoubtedly goof upon occasion, and I welcome feedback on these and related matters.

    UBC CS Home| Joel Friedman Home| Course Materials