CSE2001
Introduction to the Theory of Computation
(2011-12 Winter)
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 |
| Z |
Monday/Wednesday 14:30 - 16:00 |
SLH B |
Gordon Turpin |
MW 4:00 - 5:00 p.m. in CSEB3020 |
InstructorFirstName@cse.yorku.ca |
Tutorial
There will be a drop-in tutorial/TA-office-hour from 1 - 2 on
Wednesdays in Vari Hall 3006.
Textbook
Michael Sipser. Introduction to the Theory of Computation, Second
Edition. Thomson Course Technology, 2005. 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
- Wednesday January 4: First class.
- Monday January 30: Assignment 1 posted.
- Wednesday February 15: Assignment 1 due.
- Wednesday February 15: Midterm.
- Monday February 20 - Friday Feb 14 inclusive: reading week - no classes (no office hour).
- Friday March 9: Last day to drop the course without receiving a grade.
- Monday March 12: Assignment 2 posted.
- Monday March 26: Assignment 2 due.
- Monday April 2: Last class.
- Thursday, April 19: final exam.