CSE2001 2010-11 Summer

CSE2001
Introduction to the Theory of Computation
(2010-11 Summer)

This course introduces basic concepts of theoretical computer science, many of which find practical application. Topics include regular languages (finite automata and regular expressions), context free languages (context free grammars and pushdown automata), recursively enumerable languages (Turing machines, computability, and the Halting Problem) and, time permitting, a brief look at NP completeness.

Section and Instructor

Section	Time	Location	Instructor	Office Hours	Email Address
A	Monday 19:00 22:00	SLH E	Gordon Turpin	Monday 4:00 - 6:30 in CSE 3020	InstructorFirstName@cse.yorku.ca

Textbook

Introduction to the Theory of Computation, Second Edition

Errata

Other References

Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and Complexity. Wiley, 2001.
John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation, Second Edition. Addison-Wesley, 2001.
John C. Martin. Introduction to Languages and the Theory of Computation. McGraw-Hill, 2003.
Daniel Solow. How to Read and Do Proofs: An Introduction to Mathematical Thought Processes. Wiley, 2002.
Andrew Wohlgemuth. Introduction to Proof in Abstract Mathematics. Saunders College Publishing, 1990.

Course Evaluation

The course grade will depend on 2 assignments (20%), a midterm exam (35%) and a final exam (45%).

The following links will become active at appropriate times throughout the course.

Assignments (20%)

Midterm (35%)

Final Exam (45%)

Important Dates