**Description**

Introductory course on automata theory,
computability theory, and complexity theory.

**Instructors**

Prof. Nicholas
Harvey, Office: X851, Email: nickhar@cs.ubc.ca

**TA:** Samira Samadi

**Webpage: **http://www.cs.ubc.ca/~nickhar/F12

**Textbook**

·
M.
Sipser, Introduction
to the Theory of Computation. 3^{rd} edition preferred, 2^{nd}
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**

·
40%: Assignments

·
20%: Midterm

·
40%: Final exam

**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:

- Basic
programming notation, basic algorithms
- Asymptotic
analysis, Big-O notation
- Basic
discrete math: sets, graphs, strings

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 ﬁgure out ideas
for solving the problem. If you come up with the actual solution yourself,
that’s ﬁne. 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