Course Information (links to past and current course materials)

Course FormatCourse Goals

Course Coordinator

Textbooks and References

Prerequisites by Topic

Major Topics Covered in Course

Laboratory Projects

Covers finite-state machines and regular expressions; context-free grammars; properties and decidability problems of regular and context-free languages; pushdown automata; pumping theorems for regular and context-free languages; Turing machines, Church's thesis, and the halting problem; and applications to compilers, artificial intelligence, and pattern recognition.4 QH credit

Prerequisite: COM 1201, COM 1340, and MTH 1137.

Course is offered during the Spring and Summer quarters. CS majors are guaranteed a place in class.

Spring 2001 Summer 2001

BSCS03 required course

BSCS04 Languagecore

BACS required core

BSIS general electiveThis is a BS CS Languages core and is a required course for BA CS majors.

Professor Harriet Fell

fell@ccs.neu.edu

Spring 2000

- Michael Sipser, "Introduction to the Theory of Computation", PWS Publishing Company, Boston, 1997 (reprinted later with corrections).
- Harry R. Lewis and Christos H. Papadimitrou, "Elements of the Theory of Computation, Second Edition", Prentice Hall, Upper Saddle River, NJ, 1998.
- Daniel I. A. Cohen, "Introduction to Computer Theory, Second Edition", John Wiley & Sons, Inc., New York, 1997.
- Andrew Hodges, "Alan Turing, the enigma", Simon and Schuster, New York, 1983.
- David Brin, "Earth", Bantam Books, New York, 1990.
- Harry Harrison and Marvin Minsky, "The Turing Option", Warner Books, 1992.
- Neal Stephenson The Diamond Age", Bantam Books, New York, 1995.
- Neal Stephenson, "Snow Crash", Bantam Books, New York, 1992.
- Douglas R. Hofstadter, "Goedel, Escher, Bach", Random House, Inc., New York, 1989.

Similar Texts

Biography

Light Reading

Not-So-Light Reading

To learn about the theoretical model for computation.

- Logic
- boolean logic and sets
- sequences and tuples
- functions and relations
- propositional logic
- predicate logic
- use of proof techniques: induction, contradiction, direct proof

- They should have seen the things above but will get more practice in
this course.
- counting, principle of inclusion and exclusion
- recursive definition
- basic graph theory and algorithms

Discrete math

- They should have seen the things above but will get more practice in
this course. They really should understand breath-first search.

- Automata theory:
- automata, finite state machines
- regular expressions
- languages and grammars
- Turing machine as a formal definition of algorithm
- decidability, halting problem

Role of theory in decision making:In particular, understanding that some problems may not be tractable but that an acceptable solution may come out of heuristics or probabilistic algorithms.

There are no programming assignments (except for the honors adjunct).

There are four homework assignments, three hour exams, and a final.

This will change as students enter the course with the knowledge of Scheme (new prerequisite course COM 1340).