cse 546/646 : Intro. to Theory of Computation : Winter 2009


Text: Michael Sipser, "Introduction to the Theory of Computation", Second Edition, Thomson

Additional references:

John E. Hopcroft and Jeffrey D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley

John C. Martin, "Introduction to Languages and the Theory of Computation - Second Edition", McGraw-Hill

Other references:
Related stuff:

This course will introduce the theory of computation. We introduce the Turing machine as our basic computational model, and present some alternative models which are shown to be equivalent. We will consider decidable and undecidable problems. We will further classify problems according to time and space complexity, and establish the existence of problem classes such as P and NP.

Students will learn how to construct a Turing machine and use it in proofs; how to demonstrate undecidability; how to show that two problems are equivalent. They will acquire an understanding of the limits of digital computation.

There is no lab component to this course, but assigned work may include programming assignments.

This course combines the advanced undergraduate level cse546 and the graduate level cse646. Although the material to be covered is the same for both, students registered in cse646 will be required to demonstrate a greater depth of knowledge and understanding in assignments and tests. Students in cse646 will be assigned additional reading and written report on one of a selection of journal or conference papers relating to theory of computation, Turing Machines or complexity. This will be optional for students registered in cse546.

List of papers: (link pending
Term Project/paper: