Introduction to the Theory of Computation
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
||Monday 19:00 22:00
||Monday 4:00 - 6:30 in CSE 3020
Michael Sipser. Introduction to the Theory of Computation, Second
Edition. Thomson Course Technology, 2005. Errata.
- 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.
- 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.
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.
Final Exam (45%)
- 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