
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 uptodate 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: 1112:30pm, ICCS 104.
Dec 4:
This week we will have different office hours:
Monday (today, Dec 4): Skyler, 35pm. Tuesday: Ali, 69pm.
Wednesday: Skyler 35pm. Thursday: Joel, 23pm (ICCS 104),
Ali, 45pm.
Friday: Joel: 1112:30pm (ICCS 104), Yabing: 23:30pm (in Yabing's
usual location);
for locations for other TA office hours, see the course piazza page.
Monday, December 11: Joel: 1112: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:353: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, 23: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, 35, 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).
NonRegular Languages, the MyhillNerode Theorem, ...
(last revised October 11, 2023, 9:30am).
(We will use the MyhillNerode 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 NPcomplete, and
a similar PSPACEcomplete 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 doublesided 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 15 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,
GROUCHOMARXSELF = { p  p ∉ LanguageRecBy(p) } is not recognizable.
09_15: proof of Cantor's theorem.
NONACCEPTANCE = {  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 NOTPROGPLUSINPUT (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 "NonRegular 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 NOTPROGPLUSINPUT (as defined in
class = NONPYTHON (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 nonregular.
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
DIVBY3; start MyhillNerode Theorem.
10_13 The reverse of a language.
{0^n 1^n} is nonregular. Using the MyhillNerode Theorem to
build a minimum state DFA for: {epsilon} (2 states), and
for DIVBY3ONLY01.
10_16
Continue MyhillNerode minimum state DFA for DIVBY3ONLY01
(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}. Multitape Turing machines.
10_25
Multitape Turing machines: uses and equivalence with 1tape 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 MyhillNerode 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 CookLevin Theorem, NPcompleteness).
Board scans:
11_06
Time for Turing machines, review O(f(n)). OO(f(n)) notation.
P = polynomial time decidable languages.
CONNECTEDGRAPH an example: what is < G > for a graph, G?
11_08
CONNECTEDGRAPH is in P. Nondeterministic Turing machines.
3COLOR decidable in nondeterministic polynomial time.
11_10
Definition of NP. SAT is in NP.
Start CookLevin Theorem: SAT in P implies P = NP.
11_17
Continuation of the
CookLevin Theorem.
11_20
More precise form of the CookLevin Theorem. End of proof, including
Boolean algebra (a bit swept under the rug).
11_22
Formal definition of NPcompleteness; examples: SAT,3SAT.
SUBSETSUM is in NP; to prove SUBSETSUM is NPcomplete is suffices
to give a polynomial time reduction from 3SAT to SUBSETSUM.
11_24
Is EVEN NPComplete?
Reduction from 3SAT to SUBSETSUM.

Roughly 1 week:
Circuit and Formula Complexity (part of Chapter 9 [Sip]):
Board scans:
11_27
Remarks on showing 4SAT is NPcomplete.
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 30Nov 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: 34 pm, ICCS X139, Skyler (TA).
Tuesday: 2:304pm, ICCS X150, Table 6, Yabing (TA).
45pm, Zoom (via Canvas), Ali (TA).
Wednesday: 34 pm, ICCS X139, Skyler (TA).
Thursday: 23pm, ICCS X561 on Oct 12, Joel (Instructor).
45pm, 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 1315
(includes Remembrance Day (observed): Nov 13).
Last day of classes: Thursday, December 7 (hence Dec 6 is our last day).
Exam Period: Dec 1122.
Our final exam: Dec ??.

