Description
Introductory course on
automata theory, computability theory, and complexity theory.
Instructors
Prof. Nicholas
Harvey, Office: X851, Email: nickhar@cs.ubc.ca
TA: Sharan Rajesh Vaswani, Email: sharanv@cs.ubc.ca
Webpage: http://www.cs.ubc.ca/~nickhar/F13
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
·
30%: Midterm
·
50%: Final exam
CPSC 501 students
·
15%: Assignments
·
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