CPSC 421/501 (Introduction to Theory of Computing)

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