Description
Introductory course on automata theory,
computability theory, and complexity theory.
Instructors
Prof. Nicholas
Harvey, Office: X851, Email: nickhar@cs.ubc.ca
TAs:
·
Sikander Randhawa, sikander_94@alumni.ubc.ca
·
Curtis Fox, curtis.fox@alumni.ubc.ca
·
Shane Sims, ssims@cs.ubc.ca
Webpage:
http://www.cs.ubc.ca/~nickhar/F18-421
Textbook
· M. Sipser, Introduction
to the Theory of Computation. 1st edition is pretty old, but 2nd
and 3rd edition are almost equivalent for our purposes. The
2nd edition is available on Amazon used for $46.
· Frequently Asked Question: Is the textbook mandatory for this course?
o Answer: Realistically,
I don’t have any way to enforce whether you buy the textbook or not, so
declaring it to be “mandatory” has little consequence. I think you will
strongly benefit from having a copy of the textbook because its proofs are more
detailed than the lectures, it is extremely well written, it discusses a lot of
context of the course material, and it has more examples than we will have time
to cover. It also has useful practice problems. The CS reading room has several
physical copies.
· Frequently Asked Question: Why is the textbook so expensive?
o Short answer: The
principal-agent problem?
o Long answer:
Listen to the podcast “Why
Textbook Prices Keep Climbing”. In particular, keep in mind Mankiw’s quote
“The biggest expenditure for students is not the expenditure of money, but it's
the expenditure of their time.”
Grading Scheme
CPSC 421 students
· 20%: Assignments (best 8 out of
10)
· 30%: Midterm
· 50%: Final exam
CPSC 501 students
· 15%: Assignments (best 8 out of
10)
· 25%: Midterm
· 40%: Final exam
· 20%: Project
Prerequisites
The most important prerequisite for this course is the ability to write a
logical proof, especially an inductive proof. I also expect you to be familiar with the following
concepts:
To
review these topics, see the first chapter of the textbook, or Lehman, Leighton
and Meyer Ch 1-5, 11, 13.
Equity, Inclusion & Wellness
See
https://www.cs.ubc.ca/students/undergrad/resources/equity-inclusion-wellness
Academic Disconduct
See
https://www.cs.ubc.ca/students/undergrad/resources/academic-integrity