CPSC 421/501 Page, Fall 2025

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 essay (and possible) presentation.

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 Nov 12, 2025: Joel's office hours Nov 13, 3:10-4:25pm in ICCS 304, not his office.
Oct 28, 2025: Our midterm has been postponed to Friday, November 14. Note that Nov 10-12 is UBC's midterm break.
Classes starting Oct 29 likely resuming in-person; however, consult our course Piazza page for possible last-minute switch to Zoom.
Oct 25, 2025: Class on Oct 27 (Monday) is cancelled. Be prepared to transition to Zoom starting Oct 29 (Wednesday) if needed; links to be provided via UBC's Canvas system. Be prepared for a possible (but not very likey) delay of our midterm until Nov 7; details, in case of delay, to be posted on our course Piazza page and discussed in class.
Oct 23, 2025: Class on Oct 24 (Friday) is cancelled.
Oct 9, 2025: Typo corrected in Homework 5 (M' not M, in Problem 3(c)(i)). (No change to the content of 3(c)(i).)
Oct 7, 2025: Minor corrections to Uncomputability in CPSC 421. Midterm exam room announced below.
Sept 19, 2025: Minor corrections to Group Homework 3.
Sept 15, 2025: Group Homework 2 has no Problem~9.4.3, and has only 3 problems. Instead, there is a bonus problem. (So the total possible on this homework is 120%.) The homework deadline has been moved to Monday, Sept 22, 11:59pm.
Sept 5, 2025: Office hours announced to Piazza. Group Homework 1 due Sept 11, 11:59pm.
Sept 2, 2025: Welcome back! First class will be Wednesday, September 3, 11am-12pm.
Our course is now meeting in FNH (Food, Nutrition, and Health Building), Room 60.
Aug 29, 2025: We are currently were scheduled to meet in SHRM, Room B1009, which turns out not to be a classroom. Stay turned for a revised location.
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 2024 and Fall 2023 and 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 (1) most of Chapters 1, 3-5, and 7, (2) the parts of Chapters 8 and 9 relating to P versus NP, (3) a bit on formula complexity, starting with the work of Subbotovskaya.

Aside from the textbook, we will use some handouts (which may be revised during the course):
  • Uncomputability in CPSC421 (last revised October 6, 2025, 9:38am).
  • a DFA for the language {0,3,6,9,12,...} (this is from my 2019 course), mainly as a cautionary tale.
  • Non-Regular Languages and the Myhill-Nerode Theorem, ... (last revised in 2024). (We will use the Myhill-Nerode theorem instead of the Pumping Lemma in Section 1.4 of the textbook.)
  • Introduction to Solving P Versus NP, and Subbotovskaya's Restriction Method (last revised in 2023).

    • We may use some of these handouts used in older versions of this course (some of which may be revised for 2025):
  • Sneaky Complete Languages and Notes on Chapter 7 (last revised November 14, 2023, 9:15am)....
  • Introduction to Solving P Versus NP, and Subbotovskaya's Restriction Method (last revised December 1, 2023, 10:13am).
  • Godel's Incompleteness Theorem via Undecidability of the Halting Problem (last revised 2023). This is a WORK IN PROGRESS that is full of issues. At this point I'm just posting this as is, to give you an idea where we could go with this for this year (or in 2026, 2027, etc.).
    • Exams The midterm will take place during class hours on Friday, October 31 November 14, 2025, in SWNG 222; it will be a 45 minute exam. You will be seated in order (by last name or ID number); please remain outside the room until we ask you to enter.
    Note that Nov 10-12 is UBC's midterm break, and no office hours will be held from Friday, Nov 7 to Wed, Nov 12 -- plan ahead!
    The midterm will cover all class material up to October 17. Here is a Midterm Exam Study Guide, 2025 (this is currently a DRAFT, which will likely very closely resemble the 2024 version, since not much has changed this year). You are allowed 1 two-sided letter size (8.5" x 11") sheet of notes.

    The final will take place at 8:30am, Friday, December 19, 2025, Chemical and Biological Engineering Building (CHBE) | Floor: 1 | Room: 101. You will be allowed two double-sided sheets of 8.5" x 11" notes, handwritten or typeset.
    Readings and Boards Scans The following is the rough class plan and corresponding readings; it may be modified. Board scans will be posted for each lecture (technology willing...).
    • Roughly 2.5 weeks: Sections 1-7 of Uncomputability in CPSC421. This includes material overlapping with Section 4.2 of [Sip].
      Board scans:
      09_03: course policy, Russell's paradox, begin Cantor's Theorem (our version is more detailed that the standard statement of Cantor's Theorem).
      09_05: admin stuff regarding gradescope, Workday, and Canvas (and the lack of bijections therein), Cantor's Theorem (our version of it): example of a 3-element set. Viewing this as a diagonal of a 3 x 3 table. The imaginary student and diagonalization. Ultimate goal of applying Cantor's Theorem to the set of ASCII strings. Proof of Cantor's theorem.
      09_08: Review of Cantor's theorem as we are stating it. Strings, concatenation, conventions about listing subsets of Σ*. The bad news about ASCII* and its bijection with ℕ.
      09_10: Our interest in Cantor's theorem: S = ASCII*. Languages over an alphabet. Countably infinite: some examples and some infinite sets that aren't countable. ℚ>0 is countable.
      09_12: ℝ is uncountable. Cantor's theorem variant with a set M of movies, with |M|=4 (M={Oppenheimer,Barbie,2001: A Space Odyssey, Encounters at the End of the World}), and a subset, S, of students.
      09_15: LanguageRecBy, a map ASCII* to Power(ASCII*), based on interpreting an ASCII string as a Python program; the language recognized by a Python program. Accepting (returning "yes"), rejecting (returning "no"), and looping (doing anything else). { s | s ∉ LangRecBy(s) } is not recognized by any Python program.
      09_17: The languages (1) NOT-VALID-PYTHON-PROGRAM; (2) ACCEPTANCE, REJECTION, LOOPING, NON-PYTHON-INPUT (each ASCII string lies in exactly one of these four); (3) HALTING = ACCEPTANCE ∪ REJECTION. For p ∈ NOT-VALID-PYTHON-PROGRAM, we defined LangRecBy(p) = ∅. For any Python program p and input i, we can build a Python program p' such that (1) p' ignores its input, and (2) runs p on i (hence p' on any input accepts/rejects/loops according to whether or not p on i accepts/rejects/loops). Start Prop 4.19 of notes: Let T = { s | s ∉ LangRecBy(s) }, then for all strings q, q ∉ T iff qσ0q ∈ ACCEPTANCE.
      09_19: Recognizable versus (in the context of a Python program) decidable. NOT-VALID-PYTHON-PROGRAM is decidable. ACCEPTANCE, REJECTION, HALTING are all recognizable by a Universal Python Program. LOOPING is unrecognizable, for if it were, then T would be recognizable. (General principle, if L1,L2,L3,L4 partition ASCII*, and L1,L2,L3,L4 are recognizable, then they all are decidable.)
      09_22: Second abstract principle: L is decidable iff L and Lcomp are recognizable. If L1=NOT-VALID-PYTHON-PROGRAM, L2=ACCEPTANCE, L3=REJECTION, L4=LOOPING all recognizable, then (first abstract principle) all decidable, then then membership in T = { s | s ∉ LangRecBy(s) } for a given p can be tested by feeding pσ0p into L1,L2,L3,L4 decider, which is impossible. Hence L4 is undecidable. The difference between a proof by contradiction that gives no information, as opposed to a proof by contraction that gives an interesting fact (and an immediate contradiction). First proof that there are infinitely primes: the usual one. Second proof: the sum 1/p over all p prime diverges (I gave one idea behind the proof); corollary: there are infinitely many primes.
      09_24: Third abstract principle: L is decidable iff Lcomp is decidable. [Review decidable versus recognizable.] Hence LOOPING is unrecognizable => LOOPING is undecidable => NOT-PYTHON-INPUT ∪ ACCEPTANCE ∪ REJECTION is undecidable. ACCEPTANCE is decidable iff REJECTION is decidable. The "Berry Paradox" (likely due to Russell(?)), and another paradox.
    • 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_26: The operations concat and *. { a^2,a^9 }^*, { a^3,a^5 }^*, { a^10,a^25 }^*.
      09_29: DIV-BY-3: the language, and a number of variants. A DFA for DIV-BY-3: a very simple algorithm based on states and reading the input from left to right, stopping just after the last letter scanned. Formal definition of a DFA: (Q,Σ,δ,q0,F). Start: DFA's over the alphabet Σ={a}: necessarily a path plus a cycle.
      10_01: Examples of regular and non-regular languages for Σ={a}. {a^p|p is prime} is non-regular (consider n!+2,...,n!+n).
      10_03: Can DFA's be run in parallel? If L1, L2 are regular, then so are L1 ∪ L2, L1 ∩ L2, etc. What about L1*? Ans: (next time) NFAs. A non-regular langauge over {a,b}.
      10_06: NFA's: definitions and examples. If L1, L2 are regular, then so are L1* and L1 L2 (i.e., L1 ∘ L2).
      10_08: Converting an NFA to an equivalent DFA.
      10_10: A language recognized by an NFA that requires many more states in the the equivalent DFA. The reverse of a language and DFAs. Begin and end of regular expressions (part of [Sip] 1.3). A cautionary note about DIV-BY-3. Thm: A language is regular iff it is described by a regular expression. (Stated, "only if" explained in a few words.)
      10_15: Midterm on Oct 31: admin stuff. The Myhill-Nerode theorem over the alphabet {a,b}: [last topic covered on midterm]. Theorem written down formally: this year explained with the idea that you must merge states (see notes for acknowlegement)
      10_17: More details on The Myhill-Nerode Theorem: Part 2, Section 4, "Non-Regular Languages and the Myhill-Nerode Theorem" (handout above).
      10_20: Finish Myhill-Nerode; tips on what mistake(s) NOT to make on the exam(s): you must fully justify that different values of AccFutL(s) are different.
    • Roughly 2 weeks: Chapters 3 and 4 of [Sip] (Turing Machines).
      Board scans:
      10_22: Begin Turing machines. Admin regarding midterm, class on Oct 29, etc. Conceptual explanation of 7-tuple M=(Q,Σ,Γ,δ,q0,qacc,qrej), as a Python program whose lines are represented by Q, an infinite array of cells, etc. Conventions regarding L move from cell #1. Rem: a Turing machine with no L recognizes only regular languages.
      10_29: Goals for Turing machines: add, subtract, mult, etc., build universal Turing machines, build "delightful" and "mysterious" Tm's. [In a few classes from now: Thm 8.12 of "Uncomputability in CPSC 421": Any delightful machine does not halt on the input describing a mysterious machine; immediate corollary: the acceptance problem is undecidable.] Admin regarding midterm moved to Nov 14. 501 class presentations on lowest priority this year (given 2 missed classes). Definition of PalindromeΣ and basic examples and properties. Conventions regarding Tm diagrams. PALINDROMEΣ for Σ={a}; start Σ={a,b}.
      10_31: Where we are heading: from 1-tape Turing machines to nondeterministic and k-tape (we may cover oracle Turing machines later, but didn't mention this in class at this point), then to universal Turing machines. Mentioned that q_acc and q_rej function as return yes and return no in our Python programs earlier. PALINDROMEΣ for Σ={a,b}.
      11_03: k-tape Turing machines: ultimately: used to construct a universal Tm. Exam logistics; bring review questions to class on Wednesday and Friday (last class before the midterm). Why k-tapes? E.g,, ADDITION and MULTIPLICATION. Building a 2-tape Tm for PALINDROME. High-level description, explaining what each state is doing, plus concrete values of δ (in a list).
      11_05: accept, reject, loops, language recognized by a TM, deciders, recognizable, decidable, etc. in the context of Turing machines. The ACCEPTANCETM problem: the need to "standardize" Turing machine (i.e., their descriptions). "Standardized" DFA's. There are only countably many Turing machines, countably man DFA's (once standardized), hence there exist unrecognizable problems over any alphabet. Next up: 2-tape linear time recognizers for PALINDROME; any k-tape TM can be simulated by a 1-tape TM.
      11_07: 2-tape algorithm for PALINDROME. Midterm practice.
    • Roughly 2 weeks: Chapter 7 [Sip] (P and NP, the Cook-Levin Theorem, NP-completeness).
      Board scans:
      11_17: O(f(n)) and OO(f(n)) notation. Problems that can be decided in TIME(f(n)). 2COLOUR and 3COLOUR.
    • Roughly 1.5 weeks: How not to resolve P vs NP: Space Complexity (part of Chapter 8 [Sip]), Oracle Turing Machines, and the Baker-Gill-Solovay Theorem (part of Chapter 9 [Sip]).
      Board scans:
    • Roughly 1.5 weeks: How to (maybe) resolve P vs NP: Intro to circuit and formula complexity (part of Chapter 9 [Sip], article on Subbotovskaya's result, etc.).
      Board scans:
    Homework Homework will be assigned most weeks, typically due on gradescope at 11:59pm on Thursday; you should be able to access gradescope via Canvas. 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.
    Homework 1: Group Homework 1 is due Thursday, September 11, 11:59pm, on Gradescope. There is no individual homework for Homework 1. Solutions to Homework 1.
    Homework 2: Group Homework 2 is due Thursday, September 18, Monday, September 22, 11:59pm, on Gradescope; recent changes are indicated in red. There is no individual homework for Homework 2. Solutions to Homework 2.
    Homework 3: Group Homework 3 is due Thursday, September 25, 11:59pm, on Gradescope. There is no individual homework for Homework 3. Solutions to Homework 3.
    Homework 4: Group Homework 4 is due Thursday, October 2, Monday, October 6, 11:59pm, on Gradescope; recent changes are indicated in red. There is no individual homework for Homework 4. Solutions to Homework 4.
    Homework 5: Group Homework 5 is due Thursday, October 9, 11:59pm, on Gradescope. There is no individual homework for Homework 5. Solutions to Homework 5.
    Homework 6: Group Homework 6 is due Thursday, October 16, 11:59pm, on Gradescope. There is no individual homework for Homework 6. Solutions to Homework 6.
    Homework 7: Group Homework 7, Problems (1)--(3), are due Thursday, October 23, 11:59pm, on Gradescope. The bonus problem (4) is due Tuesday, October 28, 11:59pm, on Gradescope (the solution will not be released). There is no individual homework for Homework 7. Solutions to Homework 7.
    No homework due on October 30; instead, work on problems from our study guide to the 2025 midterm, which will appear by October 23 (and will be very similar to those of 2024, 2023, etc.)
    Homework 8: Group Homework 8, is due on Thursday, November 6, 11:59pm, on Gradescope. Solutions to the bonus problem (5) will not be released. There is no individual homework for Homework 8. Solutions to Homework 8.
    No homework due on Nov 13; instead, work on problems from our study guide to the 2025 midterm.
    Homework 9: will be assigned by November 20, and due on Thursday, November 27, 11:59pm, on Gradescope.
    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.

    At times the TA's and I will not have time to answer all Piazza questions. FOR ANY UNANSWERED QUESTIONS, this term I generally have some time right after class, and we often end a few minutes early.

    Office Hours will be announced on piazza; at times they will need to be rescheduled; so (sign up for piazza and) check there. Here is the usual schedule: Monday, Ayush, 4:30-5:30pm, Zoom only; Tuesday, Rain, 4-5pm, hybrid, locaation TBA; Wednesday, Tong, 2-3:30pm, location TBA; Thursday, Yao, 12-1:30pm, location ICCS X141; Thursday, Joel, 3:10-4:30pm, ICCS X561.
    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: Wednesday, Sept 3. Drop/Withdrawl: Monday, Sept 15. National Day for Truth and Reconciliation: Tuesday, Sept 30. Thanksgiving: Monday, Oct 13. Our midterm: Friday, Oct 31. Midterm Break: Monday, Nov 10 - Wednesday, Nov 12 (Remembrance Day: Tuesday, Nov 11). Last day of class: Friday, Dec 5. Finals: Tuesday, Dec 9 - Saturday, Dec 20. Our final exam: Dec 19, 8:30am Chemical and Biological Engineering Building (CHBE) | Floor: 1 | Room: 101

    UBC CS Home| Joel Friedman Home| Course Materials