CIT 596 – Theory of Computation
University of Pennsylvania
Spring 2010
Instructor: Donna Dietz
Office: Levine (GRW) 572
Phone: (215) 746-4223
Email: dietzd@seas.upenn.edu
Lecture: TR 1:30-3:00 Skirk. Aud.
Recitation: F 11-noon Towne 313
Office Hours: MT: 11-noon, W:10-noon, or appointment
Text: Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, 2006. ISBN-10: 0-534-95097-3 (We will make occasional use of the textbook from CIT 592, Discrete Mathematics and Its Applications, Kenneth H. Rosen, 6th edition.)
Official Course Description: - Prerequisite: CIT 592 or equivalent. Relations. Finite automata, regular languages, regular grammars, and applications. Pushdown automata, trees, context-free grammars, and applications. Turing machines. Introduction to computability and complexity theory.
Registration in both this lecture, as well as the associated recitation, is required.
Upcoming events:
Thursdays , 6-8 pm Levine
January 14
February 18
March 18
April 15
Social event for MCIT students
(Pizza will be served.)
Special Guest Speaker:
ERIC RAYMOND
Thursday, January 21st 6-8pm
Wu and Chen Auditorium
This course is part of a two-course sequence in the MCIT program. (CIT592, Mathematical Foundations of Computer Science, is the other course in this sequence.)
Grading: Your final grade for the semester will be weighted as follows: 25% each for Exam I and Exam II, 30% for the Final, and 20% for the various homeworks and/or projects which will be assigned roughly once per week during the semester. All assignments and other announcements will be posted through Blackboard.
Calendar:
This course meets 28 times for 90 minutes during the semester, plus once (2 hours) for the final exam.
|
|
date |
agenda |
agenda |
|
1 |
Th Jan 14 |
Intro, 1.1 |
Finite Automata |
|
2 |
Tu Jan 19 |
1.1 |
Regular Operations |
|
3 |
Th Jan 21 |
1.2 |
Nondeterminism, DFAs and NFAs |
|
4 |
Tu Jan 26 |
1.2 |
Closure under regular operations |
|
|
Tu Jan 26 |
12.2 Rosen |
Finite State Machines w/Output |
|
5 |
Tu Feb 2 |
1.3 |
Regular Expressions |
|
6 |
Th Feb 4 |
1.4 |
Nonregular Languages |
|
7 |
Tu Feb 9 |
2.1 |
Context-free Grammars |
|
8 |
Th Feb 11 |
Exam I |
(on material from days 1-6) |
|
9 |
Tu Feb 16 |
2.2 |
PDAs |
|
10 |
Th Feb 18 |
2.2 |
PDA=CFG |
|
11 |
Tu Feb 23 |
2.3 |
Non-context-free grammars |
|
|
Tu Feb 23 |
12.1 Rosen |
Languages and Grammars |
|
12 |
Th Feb 25 |
3.1 |
Turing Machines |
|
13 |
Tu Mar 2 |
3.2 |
TM continued... & variants |
|
14 |
Th Mar 4 |
3.3 |
Definition of Algorithm |
|
15 |
Tu Mar 16 |
4.1 |
Decidable Languages |
|
16 |
Th Mar 18 |
4.2 |
The Halting Problem |
|
17 |
Tu Mar 23 |
5.1 |
Undecidable Problems from Language Theory |
|
18 |
Th Mar 25 |
Exam II |
(on material from days 7 and 9-16) |
|
19 |
Tu Mar 30 |
5.2 |
A Simple Undecidable Problem (Post) |
|
20 |
Th Apr 1 |
5.3, 6.1 |
Mapping Reducibility, Recursion Theorem |
|
21 |
Tu Apr 6 |
6.2, 6.3 |
Decidability, Reducibility |
|
22 |
Th Apr 8 |
6.4, 7.1 |
Information, Complexity Theory |
|
23 |
Tu Apr 13 |
7.2 |
The Class P |
|
24 |
Th Apr 15 |
|
continued... |
|
25 |
Tu Apr 20 |
7.3, 7.4 |
The Class NP and NP-Completeness |
|
26 |
Th Apr 22 |
|
continued... |
|
27 |
Tu Apr 27 |
Review |
|
|
|
We May 5 9-11 |
FINAL EXAM |
(most likely will be cumulative) |