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 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)....
    • Exams The midterm will take place during class hours on Friday, October 31, 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.
    The midterm will cover all class material up to October 17.
    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 regular expressions.
    • Roughly 2 weeks: Chapters 3 and 4 of [Sip] (Turing Machines).
      Board scans:
    • Roughly 2 weeks: Chapter 7 [Sip] (P and NP, the Cook-Levin Theorem, NP-completeness).
      Board scans:
    • 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.
    Homework 6: Group Homework 6 is due Thursday, October 16, 11:59pm, on Gradescope. There is no individual homework for Homework 6.
    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 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:05-4:30pm, ICCS X561.
    Joel's office hours moved from Thursday, Oct 2, to (the next week) Monday, Oct 6, 2:30-4pm (still ICCS X561). Joel's usual office hour on Thursday, Oct 9, is unchanged.
    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.

    UBC CS Home| Joel Friedman Home| Course Materials