 |
CPSC 421/501 Page, Fall 2024
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 |
Dec 5: Office hours before exam:
Monday, Dec 9: 10-11am Allison, 11am-12pm Yao, 12-1pm Tong, 2:45-4:15pm Joel,
Locations below.
Final Exam Study Guide, 2024;
I will probably add a few more questions to this guide.
Dec 1: I have begun writing a
Final Exam Study Guide, 2024;
I will probably add a few more questions to this guide.
Nov 25: class is cancelled for Friday, Nov 29. Joel's office hours are cancelled for Thursday, Nov 28.
Oct 30: Joel's Oct 31 office hours, 3-4:15pm, will be held in ICCS 146.
Don't forget that the midterm exam will be held in IRC 6, not IRC 4.
Oct 24: A study guide to the midterm 2024 is partially complete (see below);
some extra material will be added.
Oct 20: Joel's office hours on Thursday are cancelled for this week
Oct 1: Group Homework 4 no longer exists; Problems 9.2.39 and 9.2.43
on the handout will appear on Homework 5 (see below).
Welcome back!
First class will be Wednesday, September 4;
we are currently scheduled to meet in
IRC, Floor B1, Room 4.
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 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 most of
Chapters 1, 3-5, and 7, and part of Chapters 8 and 9.
Aside from the textbook, we will use some handouts.
Uncomputability in CPSC421
(last revised October 3, 2024, 10:05am).
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 October 10, 2024, 5:44pm).
(We will use the Myhill-Nerode theorem instead of the Pumping Lemma in
Section 1.4 of the textbook.)
We may use some of these handouts
used in older versions of this course (some of which may be revised
for 2024):
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).
|
|---|
|
Exams |
The midterm will take place during class hours on
Friday, November 1, 2024,
in IRC 6
(same building, different room).
Here is a
Midterm Exam Study Guide, 2024.
You are allowed 1 two-sided letter size (8.5" x 11") sheet of notes.
Here are
solutions to 2024 midterm;
the median score was a 26.75/33=81.06%
The final will take place at 7pm on
Tuesday, December 10, 2024, in PHRM 1201.
You will be allowed two double-sided sheets of 8.5" x 11" notes, handwritten or typeset.
I am creating a
Final Exam Study Guide, 2024;
it takes the
Midterm Exam Study Guide, 2024
and adds some material.
|
|---|
|
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 3 weeks:
Sections 1-7 of Uncomputability in CPSC421.
This includes material overlapping with Section 4.2 of [Sip].
Board scans:
09_04: course policy, begin
(our version of) Cantor's Theorem.
09_06: Cantor's theorem: examples
and proof(s). Begin Generalized Cantor's theorem
(f:S->Power(B) with |B|>= |S|): examples.
Begin: yes/no tables.
09_09:
What is meant by |S|≤|B|, |S|=|B|, and |S|<|B|
for arbitrary sets S,B.
Countably infinite sets and the positive rationals.
Alphabets and strings. Uncountable sets. The empty string &espilon.
Σ^* is countably infinite for an alphabet Σ.
09_11:
Generalized Cantor's Theorem (injective form);
decision problems; there exist "unsolvable decision problems"
via uncountabilty of decision problems and countability
of "algorithms".
09_13:
The toy programming language Duck.
What it means for a Duck program to "accept" an input.
Duck-recognizable langugages, and Duck-unrecognizable languages.
LangRecBy as a map from ASCII strings to the power set of ASCII strings.
An application of Cantor's Theorem.
09_16:
Python program: conventions to define, for any string p, the
language recognized by p.
T = { p | p notin LangRecBy(p) }, both in the context of Duck programs
and Python programs.
09_18:
NON-ACCEPTANCE and NON-HALTING are unrecognizable (in the context
of Python programs). Proof uses a universal Python program, and the fact
that T = { p | p notin LangRecBy(p) } is not in the image of LangRecBy.
09_20:
Decidable versus recognizable. Partition of ASCII strings into
NON-PYTH-INP, ACCEPTANCE, REJECTION, and LOOPING.
Universal Python programs that output
"not valid", "accepts", "rejects", "loops", but may not terminate.
Universal Python programs yield a recognizer for ACCEPTANCE.
NON-ACCEPTANCE is unrecognizable (in the context
of Python programs): more details and a table.
09_23:
Why our proof that NON-ACCEPTANCE is unrecognizable is a type of
"reduction" (in the wide sense).
Duck-recognizable languages are (1) not closed under complementation,
and (2) a strict subset of Python recognizable languages.
L is decidable iff L and L complement are both recognizable.
More examples of undecidable and unrecognizable to follow...
09_25:
Two tools to produce undecidable and unrecognizable languages:
(1) L unrecognizable implies L and L^Comp are undecidable, and
(2) reductions.
Example L={p | p accepts some input} is undecidable but recognizable:
recognizing arranages all inputs as i_1,i_2,... plus one trick
(that we've already seen, in a sense).
Undecidabilty is proven with a "sneaky construction" to reduce
decidability of ACCEPTANCE to decidability of L
(i.e., L is decidable => ACCEPTANCE is decidable).
09_27:
Review {p | p accepts some input} is undecidable but recognizable.
3 or 4 "paradoxes."
Begin: regular languages (Chapter 1, [Sip]).
-
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:
10_02:
DFA's and regular languages:
{ contains "ba" as a substring}, { ends in "ba" }, DIV-BY-3,
{ a^3,a^5 }, and { a^3,a^5 }^*
10_04:
Wish list for a finite automaton recognizing {a^3,a^5}^*.
Transitions to zero possible state,
transitions to more than one possible state; ε transitions or
"jumps". Non-determinism and NFA's. For each NFA there is a DFA.
10_07:
Review motivation for NFA via {a^3,a^5}^* .
How to use NFA's to recognize L_1 ∪ L_2,
L_1 ￮ L_2.
Regular expressions.
More on NFA to DFA.
10_09:
Remark: NFA's have a polynomial time implementation.
Thm: A language is regular iff it is described by a regular expression.
A cautionary note about DIV-BY-3.
Non-regular languages over the alphabet {a}, eventual periodicity.
10_11:
Formal definitions for DFA's and languages over {a}:
DFA's: path plus cycle; Languages: the eventual period of a language.
Classification of regular languages. Finite languages have eventual
period 1.
Famous open problem: is {a^n | n and n+2 are prime} a regular language?
10_16:
The Myhill-Nerode theorem.
First example: {a^n | n is 1 or n is a positive even integer}.
Second example: {a^(n^2) }.
10_18:
The Myhill-Nerode theorem over the alphabet {a,b}:
{a^n b^n} is non-regular; strings whose last letter is an "a";
strings whose 2nd to last letter is an "a".
-
Roughly 2 weeks:
Chapters 3 and 4 of [Sip] (Turing Machines).
Board scans:
10_21: Begin Turing machines. Intuitive
explanation as a DFA with a read/write tape and a movable tape head.
Formal definition as a tuple. L = {a,b}^* a.
10_23: Turing machines: accepting,
rejecting, looping, recognizing, deciding (similar to Python programs).
A Turing machine for PALINDROME.
10_25: Multi-tape Turing machines.
Linear time 2-tape Turing machine algorithm for PALINDROME.
10_28: Multi-tape Turing machines:
our goals: addition/ADDITION and multiplication/MULTIPLICATION,
Acceptance DFA and Acceptance TM. Midterm logistics.
Start: addition/ADDITION and
multiplication/MULTIPLICATION (and functions versus decision problems).
Review question on practice midterm: {all maps of naturals to {1,2} }
is uncountable.
10_30: Multi-tape Turing machines:
Multiplication/MULTIPLICATION.
A multi-tape Turing machine can be simulated by a one-tape machine.
Review question on practice midterm: the set of regular languages is
countable (via counting all DFA's or counting all regular expressions);
if L_1,L_2 is unrecogniable, then their union is not necessarily
unrecognizable.
11_04: Acceptance problem from Duck.
Standardized DFA's, Acceptance problem for DFA's.
11_06: A T.m. "code snippet" that will
be assigned on the next homework (a counter), and its relevance to
algorithms and acceptance problem.
Acceptance problem of DFA's and for Turing machines,
in the context of Turing machines.
-
Roughly 2 weeks:
Chapter 7 [Sip] (P and NP, the Cook-Levin Theorem, NP-completeness).
Board scans:
11_08: Remarks on Chapter 7-9 of [Sip].
Review Big-O and small-o notation.
"Time" for Turing machines = # computation steps.
P = polynomial time for Turing machines.
Claim: P = poly time for algorithms in Python.
Describing graphs, BIPARTITE = 2COLOUR, and 3COLOUR; all have an exponential
time ("exhaustive") algorithm. Polynomial time algorithm for 2COLOUR.
How to earn $1,000,000 (USD, before taxes): Is 3COLOUR in P or not?
11_15:
SAT = set of satisfiable Boolean formulas in the variables x_1,...,x_n.
For each standardized graph, G, we find a Boolean formula, f, such that
G is in 3COLOUR iff f is in SAT; furthermore the size of the description
of f will be linear in the size of the description of G (at least if G
is connected). Note: for students having taken CPSC 320, this is a
reduction of 3COLOUR to SAT.
11_18:
Boolean algebra, DNF and CNF formulas. Review O-notation, o-notation,
and OO-notation (pronounced "uh-oh," and I believe due to Udi Manber).
The "canonical DNF form" of a Boolean function on n variables, of size
at most n times 2^n. CNF and 3-CNF forms.
11_20:
Start: the Cook-Levin theorem: Definition of Non-deterministic Turing
machine and NP. Some subtleties. Explain SAT, 3COLOUR are in NP.
Formal definition of poly-time reduction.
Lemma: a disjuction of 4 Boolean values is equivalent to the satisfiability
of a 3CNF with two clauses.
11_22:
The Cook-Levin theorem: setting up the Boolean variables to describe
a non-deterministic Turing machine running in polynomial time; overall
description of the formula, and some details.
(You will also find the variables described in Section 1 of
Sneaky Complete Languages and
Notes on Chapter 7.)
-
Roughly 1 week:
Space Complexity (part of Chapter 8 [Sip]).
Board scans:
Scans for 11_25 and 11_27: TQBF (True
Quantified Boolean Formulas): how to solve them in (exponential time
but only) linear space. How to define sublinear space (with a 2nd
worktape), PSPACE, NPSPACE, L, NL. PSPACE and NPSPACE are contained in
EXPTIME. Savitch's Theorem NSPACE(s(n)) is in DSPACE(s(n)^2); hence
PSPACE = NPSPACE. Rough idea why TQBF is PSPACE-complete.
-
Roughly 1 class:
Circuit and Formula Complexity (part of Chapter 9 [Sip], article on
Subbotovskaya's result).
Board scans:
12_02:
How not to prove Fermat's last theorem.
How not to resolve P vs. NP (summary of the Baker-Gill-Solovay Theorem),
i.e., overview of Oracle Turing Machines, P^A = NP^A where A is any
PSPACE-complete problem, and P^B != NP^B for some language B.
How to resolve P vs. NP: circuit complexity; even easier question,
yet very difficult: formula complexity; statement of Subbotovskaya's
1961 result on XOR and formula size (see handout above for details...).
-
Roughly 2 classes:
12_04: CPSC 501 presentation;
questions from final exam study guide.
12_06: Office hours on Monday, questions from
final exam study guide.
|
|---|
| 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 12, 11:59pm, on Gradescope.
FWIW, here is
a LaTeX file
that shows the way I generated the first
few homework problems.
Solutions to Homework 1.
Homework 2:
No individual homework this week.
Here is
Group Homework 2.
Group homework is due Thursday, September 19, 11:59pm, on Gradescope.
Solutions to Homework 2.
Homework 3:
No individual homework this week.
Here is
Group Homework 3.
The first two problems of
Group homework are due Thursday, September 26, 11:59pm, on Gradescope.
The last two problems are due Thursday, October 3, 11:59pm.
(You should have received a message from me via Workday regarding this
on Sept 20; it was also announced on Piazza at the time).
Solutions to Homework 3,
first two problems.
Solutions to Homework 3,
last two problems.
Homework 4:
No group homework this week.
Here is
Individual Homework 4,
due Thursday, October 3, 11:59pm.
Solutions.
Homework 5:
Here are
Individual Homework 5
and
Group Homework 5,
both due Thursday, October 10, 11:59pm.
Solutions to the
Individual HW 5 and
Solutions to the
Group HW 5.
Homework 6:
There is no individual homework this week. Here is
Group Homework 6,
due on Thursday, October 17, 11:59pm.
Solutions to Homework 6.
Homework 7:
There is no individual homework this week. Here is
Group Homework 7,
due on Thursday, October 24, 11:59pm.
Solutions to Homework 7.
No homework due on October 31; instead work on problems from our
study guide to the 2024 midterm.
Homework 8:
There is no individual homework this week. Here is the short
Group Homework 8,
to be due Sunday, November 17, 11:59pm (due to midterm break).
Solutions to Homework 8.
Homework 9:
There is no individual homework this week. Here is
Group Homework 9,
due on Monday, November 25, 11:59pm.
Homework 9 will be the last homework set that we collect
and grade this term.
Solutions to Homework 9.
Homework 10.5:
Here are some homework problems regarding class material covered
Nov 18-27; they will not be collected or graded.
Group Homework 10.5.
Solutions to Homework 10.5.
|
|---|
|
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, week of Dec 9-13:
SEE THE COURSE PIAZZA PAGE FOR:
time, location and any last minute changes;
any announcement by Joel and the
TA's on Piazza supercedes the schedule below:
Monday, Dec 9: 10-11am Allison, 11am-12pm Yao, 12-1pm Tong, locations TBA.
2:45-4:15pm Joel, ICCS 304.
|
|---|
| 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 4.
Drop/Withdrawl without W: Sept 16.
National Truth and Reconciliation Day (no class): Sept 30.
Thanksgiving: Oct 14.
Our midterm: Friday, Nov 1.
Midterm Break: Nov 11-13
(includes Remembrance Day (observed): Nov 11).
Last day of classes: Friday, Dec 6.
Exam Period: Dec 10-21.
Our final exam: Tuesday, Dec 10, 7pm
|
|---|
|