Description
Introductory course on automata theory,
computability theory, and complexity theory.
Instructors
Prof. Nicholas
Harvey, Office: X851, Email: nickhar@cs.ubc.ca
TAs:
·
Bader Alahmad,
bader@ece.ubc.ca
·
Devon Graham, drgraham@cs.ubc.ca
·
Chris Liaw,
cvliaw@cs.ubc.ca
Webpage: http://www.cs.ubc.ca/~nickhar/F16
Textbook
· M. Sipser, Introduction
to the Theory of Computation. 3rd edition preferred, 2nd
edition also OK.
· Frequently Asked Question: Is the
textbook mandatory for this course?
o Short answer: Yes.
o Long answer: Yes.
This is a superb book. I would rank it as one of the top-three best-written
computer science texts that I know of. Unfortunately it is quite expensive.
Fortunately I am allowing you to use the older edition which you can probably
find used. Unfortunately that is probably expensive too. There are two reasons
that it is mandatory: (1) the exercises will be taken from this book, and (2)
for the purposes of the exams, you will be responsible for knowing the material
in the relevant sections of the text. I cannot guarantee that my coverage of
the material in class will be as comprehensive as the coverage in the textbook.
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.
Academic Misconduct
Submitting
the work of another person, whether that be another student, something from a
book, or something off the web and representing it as your own is plagiarism
and constitutes academic misconduct. If the source is clearly cited, then it is
not academic misconduct. If you tell me “This is copied word for word from Jane
Foo’s solution” that is not academic misconduct. It will be graded as one
solution for two people and each will get half credit.
I
encourage you to discuss the homework problems with each other outside of
class. You can help each other understand the concepts and techniques needed to
solve the problems, and you can brainstorm together to figure out ideas
for solving the problem. If you come up with the actual solution yourself,
that’s fine. If you’re brainstorming with some friends and the key idea
comes up, that’s OK too – in this case, just add a note to your solution that
says something along the lines of “{Names of people in brainstorm session} and
I were discussing this problem together and came up with the idea of {state the
key idea from the brainstorm here}”.
If
you say that you got it off of the web or from another text, you’ll be graded
by the extent to which your solution shows that you actually understood the
solution that you found and were able to reformulate it using your own
reasoning.
If
you get a solution by any means other than working it out yourself and don’t
disclose it, then I will follow the university procedures for academic
misconduct.
Please
read Cheating: The List Of
Things I Never Want To Hear Again
http://www.cs.ubc.ca/~tmm/courses/cheat.html