CS311 Fall 2006

Computer Science Mount Holyoke College
CS311 Theory of Computation, Fall 2006


Instructor: Class Meets: Classroom: Office Hours: Office: Email:	Professor Xiaoyan Li M, W 11:00 AM-12:15 PM, Fri 11:00-11:50AM Kendade Hall 303 T,Th 10:00-11:00 AM Clapp 227 xli@mtholyoke.edu

Course Update Information

September 08. First Day of Class. Welcome all!

Course Objectives

Are there any limits to what computers can do? Does the answer to this question depend on whether you use a PC or a MacIntosh? This course explores issues such as these by investigating several models of computation, exploring the power and limitations of each of these models, and relating these models to typical computational problems. Topics include finite state automata, pushdown automata, grammars, Turing machines, the Universal Turing Machine, and computability.

Textbook

Introduction to the Theory of Computation, Second Edition, Michael Sipser, published by Course Technology.

Prerequisites

CS 101 and MATH 232

Schedule

The following schedule is based on Fall 2006 academic calendar:


Date	Planned Lecture Topics	Read/Assign/Exam
Sep 8 (F)	Introduction	Ch.0
Sep 11 (M) Sep 13 (W) Sep 15 (F)	FINITE AUTOMATA NONDETERMINISM	Ch. 1.1 Ch. 1.2, HW1
Sep 18 (M) Sep 20 (W) Sep 22 (F)	REGULAR EXPRESSIONS RE,NFA and GNFA	Ch. 1.3 Ch. 1.3, HW1 due
Sep 25 (M) Sep 27 (W) Sep 29 (F)	PUMPING LEMMA CONTEXT-FREE GRAMMARS	Ch. 1.4, HW2 Ch. 2.1
Oct 02 (M) Oct 04 (W) Oct 06 (F)	PUSHDOWN AUTOMATA NON-CONTEXT-FREE LANGUAGES	Ch. 2.2, HW2 due Ch. 2.3, HW3
Oct 09 (M) Oct 11 (W) Oct 13 (F)	Break Review 1
Oct 16 (M) Oct 18 (W) Oct 20 (F)	In-Class Exam 1 TURING MACHINES	Ch. 3.1 HW4
Oct 23 (M) Oct 25 (W) Oct 27 (F)	VARIANTS OF TURING MACHINES Church-Turing Thesis	Ch. 3.2, 3.3 Ch. 4.1
Oct 30 (M) Nov 01 (W) Nov 03 (F)	DECIDABLE LANGUAGES THE HALTING PROBLEM	Ch. 4.1 Ch. 4.2 HW5 (HW4 due)
Nov 06 (M) Nov 08 (W) Nov 10 (F)	Reducibility (I) No Class	Ch. 5.1
Nov 13 (M) Nov 15 (W) Nov 17 (F)	Reducibility (II) Review 2	Ch. 5.3 (HW5 due)
Nov 20 (M) Nov 22 (W) Nov 24 (F)	In-class Exam 2 Thanksgiving Break
Nov 27 (M) Nov 29 (W) Dec 01 (F)	Time Complexity (I) No Class	Ch. 7.1
Dec 04 (M) Dec 06 (W) Dec 08 (F)	Time Complexity(II) Time Complexity (III)	Ch. 7.2 HW6 Ch. 7.3
Dec 11 (M) Dec 13 (W) Dec 15 (F)	Space Complexity Review 3	Ch. 8 (HW6 due)
Dec 16-20	Final Exam

Assignments and Grading

See syllabus above for the tentative timetable for a schedule. There will be about seven assignments distributed roughly every two weeks (counted roughly 30% of your final grade). Two in-class exams will add up to 30 % of your final grade. There will be one final exam (20% of your final grade). The rest 20% goes to class participations.

Policies: Students may discuss ideas together. But since each student get credits for her submissions, all solutions must be done separately by each student, and must not be shared.

Communications: I would like the course to run smoothly and enjoyably. Feel free to let me know what you find good and interesting about the course. Let me know as soon as possible about the reverse. You may see me in my office during my hours or send me messages by e-mail.