Fall 2015

**Instructor:**
William D Clinger

**Home page:**
```
http://www.ccs.neu.edu/course/cs3800f15wc/
```

**Piazza signup:**
```
https://piazza.com/northeastern/fall2015/cs3800honors
```

**Piazza:**
```
https://piazza.com/northeastern/fall2015/cs3800honors/home
```

**Course Directory:**
`/course/cs3800f15wc`

(on the CCIS shared file system)

**Required Textbook:**
Michael Sipser
Introduction to the Theory of Computation, Third Edition.
Cengage Learning, 2013.

Introduces the theory behind computers and computing aimed at answering the question: "What are the capabilities and limitations of computers?" Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, non-determinism, non-regular languages, context-free languages, pushdown automata, and non-context-free languages. The computability portion includes Turing machines, the Church-Turing Thesis, decidable languages, and the Halting Theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P versus NP question, and NP-completeness.

Prerequisites: CS 2510

Recommended: CS 1800 (discrete structures) and CS 2800 (logic and computation)

Homework will be assigned on an almost-weekly basis. Honors students will be required to present some of their solutions to homework problems to the rest of the class.

Here are a few hints on doing homework:

**Start early.**Difficult problems are seldom solved in one sitting. The sooner you start on a problem, the more time your brain will have to think about it.**Be rigorous.**If your solution is not rigorous enough to convince the other students and the instructor of its correctness, then it is not a solution.**Be concise.**Do not belabor the obvious, but do not skip any of the essential ideas.**Talk to others.**Talking to other students may help you to understand a problem or to come up with an idea for its solution. On the other hand, you are not allowed to show your written solution to any other student(s), and you are not allowed to read a solution written by any other student(s).

All work submitted for credit must be your own. You may discuss any homework problem with your classmates and the instructors, but you must write up your own solutions. When you submit a written solution, your solution must begin with a list of all students with whom you discussed the problem, even if you don't think those discussions contributed to your solution of the problem. You must also acknowledge any written sources (apart from the textbook) that you consulted, including sources found on the World-Wide Web. You are not allowed to read solutions to previous years' assignments or to another section's assignments.

Failure to acknowledge oral discussions or written sources constitutes plagiarism, which is a form of academic dishonesty forbidden by Northeastern University's Academic Integrity Policy and the university's Code of Student Conduct.

Homework and class presentations will account for approximately 40% of your final grade. The rest of your final grade will be determined by the exams.

Every student will need a CCIS student account.

Every student will need to sign up for the Piazza course site.

Last updated 10 September 2015.

For debugging: Click here to validate.