CPSC 421/501 Page, Fall 2023

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

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 Dec 11: Some typos in the supplemental practice problems for the final exam 2023 were detected by the students and are corrected. The solutions to these problems remain unchanged.
Last office hours today: 11-12:30pm, ICCS 104.

Dec 4: This week we will have different office hours: Monday (today, Dec 4): Skyler, 3-5pm. Tuesday: Ali, 6-9pm. Wednesday: Skyler 3-5pm. Thursday: Joel, 2-3pm (ICCS 104), Ali, 4-5pm. Friday: Joel: 11-12:30pm (ICCS 104), Yabing: 2-3:30pm (in Yabing's usual location); for locations for other TA office hours, see the course piazza page. Monday, December 11: Joel: 11-12:30pm (ICCS 104).

Dec 3: A Final Exam Study Guide 2023, has appeared; some content may be added over the next day or two.

Nov 22: Joel's office hours on Thursday, Nov 23 moved to 2:35-3:35pm.

Nov 14: New handout "Sneaky Complete Languages and Notes on Chapter 7" available on this webpage; this will be used for our coverage of [Sip], Chapters 7 and 8.

Nov 9: Group Homework 8, Problem 3 has some corrections, and I have exchanged parts (a) and (b) (since this is more logical). Please note that for all Group Homework, you must make only 1 submission per group, and you must state who is in your group when you submit the homework.

Nov 2: Correction to solutions of some midterm practice (2021,4), correction indicated in red ink; thanks to Mathias!

Oct 31: My (Joel's) office hours Nov 2 are Thursday, 2-3:15pm, room ICCS 104. For TA office hours Oct 31 - Nov 2, please consult announcements on Piazza.

Oct 25: The midterm will be given during class hours on Friday, November 3, 2023. Location: our usual classroom. For more details, see the Midterm Study Guide 2023. More details on our midterm can be found

Oct 23: Due to injury, Skyler's office hours will be held (temporarily) via Zoom. See the course piazza page for details.

Oct 19: Our Final Exam time/date has been posted: Mon Dec 11, 2023, 3:30 pm. In case of extreme weather we will follow UBC's rescheduling timeline for the final exam.

Welcome back! First class will be Wednesday, September 6, Pharmaceutical Sciences Building, Room 1201.
There will be an online discussion of this course on piazza, and homework will be likely be graded using gradescope. You will likely be able to access both through UBC's Canvas system.
Overview and Course Policy 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 my CPSC 421/501 courses from previous years: Fall 2021 and Fall 2020 and Fall 2019; the material covered differs a bit each year.
References: Textbook and Handouts The required course textbook is "Introduction to the 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 likely use:
  • Uncomputability in CPSC421 (last revised October 11, 2023, 1:13pm).
  • Non-Regular Languages, the Myhill-Nerode Theorem, ... (last revised October 11, 2023, 9:30am). (We will use the Myhill-Nerode theorem instead of the Pumping Lemma in Section 1.4 of the textbook.)
  • a DFA for the language {0,3,6,9,12,...} (this is from my 2019 course), mainly as a cautionary tale.
  • Sneaky Complete Languages and Notes on Chapter 7 (last revised November 14, 9:15am) descirbes (1) some minor differences between Chapter 7 of [Sip] and the way we cover this material in CPSC 421/501, and (2) a language that is easily proven to be NP-complete, and a similar PSPACE-complete language.
  • Introduction to Solving P Versus NP, and Subbotovskaya's Restriction Method gives notes for the week of Nov. 27 to Dec. 1. The appendices were not covered, and we only stated the resuls of Section 4.
    • Exams The midterm took place during class hours on Friday, November 3, 2023. Here is the 2023 midterm and solutions; we will only regrade a problem if we have made a significant grading error.

    Our final exam will take place on December 11, 3:30pm, in DMP 310. You will be allowed two double-sided sheets of 8.5" x 11" notes, handwritten or typeset.

    The Final Exam Study Guide 2023, is being created (more material may be added); it takes the Study Guide for the Midterm 2023 and adds some material.
    Readings and Boards Scans The following is the rough class plan and corresponding readings; it may be modified.
    • Roughly 2 weeks: Sections 1-5 and some of Section 6 of Uncomputability in CPSC421. This includes material overlapping with Section 4.2 of [Sip].
      Board scans: 09_06: course policy, alphabets and strings, first look at Cantor's Theorem.
      09_08: Cantor's Theorem and Generalized Cantor's Theorem.
      09_11: Languages, examples of "decision problems" and "(Python) algorithms."
      09_13: the function LanguageRecBy, GROUCHO-MARX-SELF = { p | p ∉ LanguageRecBy(p) } is not recognizable.
      09_15: proof of Cantor's theorem. NON-ACCEPTANCE = { | i does not accept p } is unrecogizable. [Class began with demo of verysilly.py (which returns "yes" on inputs representing integers <= 5, and otherwises goes into an infinite loop or crashes), and the very basic Python debugger, invoked by "python -m pdb verysilly.py", which we used to step through "verysilly.py" one step (i.e., one program line) at a time.]
      09_18 Reductions, deciders and decidablity versus recognizability. ACCEPTANCE = { < p,i > | i accepts p } is recogizable but undecidable. We also recalled verySilly.py.
      09_20 Running Python progs in parallel: L and L complement recognizable implies that both are decidable; ACCEPT_SOME_INPUT is recognizable. Contradictions and paradoxes; "Berry paradox" and Russell's (most famous) paradox.
      09_22 NOT-PROG-PLUS-INPUT (is decidable), Russell's (famous) paradox; first example of a regular language.
    • Roughly 2 weeks: Chapter 1 of [Sip] (Regular languages); we will replace the Pumping Lemma in Section 1.4 with the handout "Non-Regular Languages,..." 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,...} (this is from my 2019 course).
      Board scans: 09_27 NOT-PROG-PLUS-INPUT (as defined in class = NON-PYTHON (as defined on the handout), formal definition of a DFA, the language a DFA recognizes, and of regular language. Analogs between DFA, states, etc., and Python programs. Examples: strings over {0,1,...,9} representing integers divisible by 3; similarly for divisible by 10. An example of merging states of a DFA to get a smaller DFA (and an example of where this leads to a slightly different language).
      09_29 Union, concatenation, star: definition and motivation. {a^3,a^5}^* consists of a^0,a^3,a^5,a^6, and a^n for n >= 8. The languages {a^5,a^7}^* and {b^6,b^10}^*. A DFA's over {a} and peroidicity for inputs of large length. {a^1,a^4,a^9,a^16,...} is non-regular. National Truth and Reconciliation Day observed on Monday.
      10_04 NFA's, examples from {a^3,a^5}^* and unions of two languages. Start: Each NFA recognizes a regular language: construction via Power(Q). Question: can NFA's be efficiently implemented?
      10_06 Graph theoretic terminology: directed graphs, paths, cycles. More on DFA's over the alphabet {a}. A bit on NFA's.
      10_11 Regular expressions and NFA's.
      10_12 Cautionary tale about DIV-BY-3; start Myhill-Nerode Theorem.
      10_13 The reverse of a language. {0^n 1^n} is non-regular. Using the Myhill-Nerode Theorem to build a minimum state DFA for: {epsilon} (2 states), and for DIV-BY-3-ONLY-0-1.
      10_16 Continue Myhill-Nerode minimum state DFA for DIV-BY-3-ONLY-0-1 (6 states).
    • Roughly 1.5 Weeks: Chapter 3 of [Sip] (Turing Machines).
      Board scans: 10_18 Begin Turing machines: definitions and intuition, (Turing-)recognizable and (Turing-)decidable languages.
      10_20 Turing machine examples: (1) last letter equals "a", (2) PALINDROME_{a,b}.
      10_23 Turing machine for PALINDROME_{a,b}. Multi-tape Turing machines.
      10_25 Multi-tape Turing machines: uses and equivalence with 1-tape TM's.
    • Roughly 1.5 Weeks: Chapter 4 of [Sip] (Universal Turing machines, undecidable and unrecognizable problems).
      Board scans: 10_27 Midterm logistics. Standard(ized) Turing machines. Begin universal Turing machines.
      10_30 Universal Turing machines. ACCEPTANCE_TM is recognizable. Part of Myhill-Nerode computation for for {ab}{abab}^* .
      11_01 If H recognizes ACCEPTANCE_TM, and D satisfies Result(D, < M>)= ¬ Result(H, < H > ), then H must loop on < D, < D > > . ACCEPTANCE_TM is undecidable. Some practice midterm questions.
    • Roughly 1.5 weeks Chapter 7 [Sip] (P and NP, the Cook-Levin Theorem, NP-completeness).
      Board scans: 11_06 Time for Turing machines, review O(f(n)). OO(f(n)) notation. P = polynomial time decidable languages. CONNECTED-GRAPH an example: what is < G > for a graph, G?
      11_08 CONNECTED-GRAPH is in P. Non-deterministic Turing machines. 3COLOR decidable in non-deterministic polynomial time.
      11_10 Definition of NP. SAT is in NP. Start Cook-Levin Theorem: SAT in P implies P = NP.
      11_17 Continuation of the Cook-Levin Theorem.
      11_20 More precise form of the Cook-Levin Theorem. End of proof, including Boolean algebra (a bit swept under the rug).
      11_22 Formal definition of NP-completeness; examples: SAT,3SAT. SUBSET-SUM is in NP; to prove SUBSET-SUM is NP-complete is suffices to give a polynomial time reduction from 3SAT to SUBSET-SUM.
      11_24 Is EVEN NP-Complete? Reduction from 3SAT to SUBSET-SUM.
    • Roughly 1 week: Circuit and Formula Complexity (part of Chapter 9 [Sip]):
      Board scans: 11_27 Remarks on showing 4SAT is NP-complete. Formulas and circuits, in arithmetic and Boolean algebra. P = NP implies SAT has polynomial size circuits (this is the main point of 9.3 of [Sip]).
      11_29 The formula size challenge for Boolean functions; example: threshold functions. More on P versus NP and the circuit size challenge for Boolean functions.
      12_01 Partity has O(n^2) formula size. Subbotovskaya's method of restrictions, and n^(3/2) lower bound of formula size for parity.
    • Parts of last 2 classes: 12_04 Final exam prep and office hours this week and next.
      12_06 5th T/F of Question 1, Part 1, Final 2021; what was covered in 2023 but not in 2021.
    Homework Homework will be assigned most weeks, typically due on gradescope at 11:59pm on Thursday. 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.
    Individual and group homework will be assigned.
    Homework 1: No individual homework this week. Here is Group Homework 1. Group homework is due Thursday, September 14, 11:59pm, on Gradescope. Solutions to Homework 1.
    Homework 2: No individual homework this week. Here is Group Homework 2. Group homework is due Thursday, September 21, 11:59pm, on Gradescope. Solutions to Homework 2.
    Homework 3: Individual Homework 3 and Group Homework 3 are due on September 28, 11:59pm, on Gradescope. Solutions to Homework 3.
    Homework 4: No individual homework this week. Here is Group Homework 4. Group homework is due Thursday, October 5, 11:59pm, on Gradescope. Solutions to Homework 4.
    Homework 5: No individual homework this week. Here is Group Homework 5. Group homework is due Thursday, October 12, 11:59pm, on Gradescope. Solutions to Homework 5.
    Homework 6: Individual Homework 6 and Group Homework 6 are due on Thursday, October 19, 11:59pm, on Gradescope. Solutions to Homework 6.
    Homework 7: Individual Homework 7 and Group Homework 7 are due on Thursday, October 26, 11:59pm, on Gradescope. Solutions to Homework 7.
    No homework due the week of Oct 30-Nov 3. Instead, study for the midterm; sample questions will be posted.
    Homework 8: Individual Homework 8 and Group Homework 8 are due on Thursday, November 16, 11:59pm, on Gradescope. Solutions to Homework 8.
    Homework 9: No individual homework this week. Here is Group Homework 9 (typo corrected 4:58pm, Nov 21). Group homework is due Thursday, November 23, 11:59pm, on Gradescope. Solutions to Homework 9.
    Homework 10: No individual homework this week. Group Homework 10 is due Thursday, November 30, 11:59pm, on Gradescope. Solutions to Homework 10.
    Homework 11: Group Homework 11 will not be collected or graded; you should aim to finish it by Thursday, December 7. It is the last homework set of the term. Solutions to Homework 11.
    Piazza and Office Hours There will be an online discussion of this course on www.piazza.com; signing up to our course piazza site will likely involve UBC's Canvas system. Please post all questions related to the course material to our piazza site.
    Office hours:
    Monday: 3-4 pm, ICCS X139, Skyler (TA).
    Tuesday: 2:30-4pm, ICCS X150, Table 6, Yabing (TA). 4-5pm, Zoom (via Canvas), Ali (TA).
    Wednesday: 3-4 pm, ICCS X139, Skyler (TA).
    Thursday: 2-3pm, ICCS X561 on Oct 12, Joel (Instructor). 4-5pm, Zoom (via Canvas), Ali (TA).
    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 Centre, privileged to work with the Musqueam First Nation; this also includes 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.
    Relevant Dates Class Starts: Sept 6. Drop/Withdrawl without W: Sept 18. Class cancelled by instructor: Sept 25. National Truth and Reconciliation Day (observed, no class): Oct 2. Thanksgiving: Oct 9.

    Makeup Monday on Thursday, Oct 12: our class (and all Monday classes) meet at its usual time on "makeup Monday," which is Thursday, Oct 12. Hence CPSC 421/501 meets on Wednesday, Thursday, and Friday of this week.

    Our midterm: Friday, Nov 3. Midterm Break: Nov 13-15 (includes Remembrance Day (observed): Nov 13). Last day of classes: Thursday, December 7 (hence Dec 6 is our last day). Exam Period: Dec 11-22. Our final exam: Dec ??.

    UBC CS Home| Joel Friedman Home| Course Materials