## 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

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

- Monday May 2: First class.
- Monday May 23: Victoria Day. No classes.
- Monday May 30: Assignment 1 posted.
- Monday, June 20: Assignment 1 due.
- Monday June 20: Midterm.
- Tuesday July 5: Last day to drop the course without receiving a grade.
- Monday, July 11: Assignment 2 posted.
- Wednesday July 20: Assignment 2 due.
- Monday July 25: Last class.
- Friday August 5, 9:00 a.m. - 12:00 noon in CSE-B: final exam