CSE 322 Introduction to Formal Models in Computer Science, Autumn 2008
Meets: Monday, Wednesday, and Friday 1:30-2:20pm in EEB 037
|
|
|
Office Hours |
Location |
Phone |
| Instructor: |
Dave Bacon |
dabacon at cs |
| Monday 2:30-3:00 | | Wednesdays 11:00-12:00 | | Friday 12:00-1:00 | | or by appointment |
|
CSE 460 |
221-6503 |
| TAs: |
Alice Neels |
neelsa at cs |
CSE 216 |
Thursday 11:30-12:20 |
|
|
Aaron Miller |
ajmiller at cs |
CSE 216 |
Thursday, 1:30-2:20 |
|
Final Exam: The final exam is Monday, Dec. 8 from 2:30-4:20 p.m. in EEB 037. It is closed notes, no calculators needed. There will be a review session in class on Friday, Dec. 5. A list of topics and sample finals are located on the sidebar
Midterm: The midterm is Wednesday, October 29, in class. It is closed notes, no calculators needed. Midterm topics as well as sample midterms on located on the sidebar. There will be a review session Sunday, Oct 26 at 4:30pm in EEB 037.
Textbook: Michael Sipser, Introduction to the Theory of Computation, PWS Publishing, Second Edition. First edition is also okay. International edition may cause problems since the problem numbers won't be properly listed on homeworks. (Second edition errata: first printing. First edition errata: first printing , later printings .)
Class Mailing List: You are responsible for signing up for and keeping up to date with the class mailing list. Subscribe here. Post your questions or comments here as well.
Feedback: Can be provided anonymously via this form.
Grading: Homework: 55%, Midterm: 20%, Final: 25%
Collaboration/Cheating Policy: See here.
Calendar:
| Week |
Monday |
Wednesday |
Friday |
1
Reading:
0.1-0.4,1.1
|
|
|
Sep. 23 |
Lecture 1
Welcome and Introduction |
Sep. 26 |
Lecture 2
Finite Automata
Formal definition
|
2
Reading: 1.2
|
Sep. 29 |
Lecture 3
Finite Automata
Regular operations
|
Oct. 1 |
Lecture 4
Nondeterministic Finite Automata
|
Oct. 3 |
Lecture 5
Equivalence Between NFA and DFA
|
3
Reading: 1.3
|
Oct. 6 |
Lecture 6
Closure Properties of FA
Homework 1 due
|
Oct. 8 |
Lecture 7
Regular expressions
|
Oct. 10 |
Lecture 8
Regular expressions and DFAs
Homework 2 due
|
4
Reading: 1.4
|
Oct. 13 |
Lecture 9
Regular expressions and DFAs
| Oct. 15 |
Lecture 10
Pumping Lemma for DFAs
|
Oct. 17 |
Lecture 11
Pumping Lemma for DFAs
Homework 3 due
|
5
Reading: 2.1
|
Oct. 20 |
Lecture 13
Myhill-Nerode
|
Oct. 22 |
Lecture 12
Myhill–Nerode Theorem
|
Oct. 24 |
Lecture 14
DFA Minimization/Pattern Matching
Homework 4 due
|
6
Reading: 2.1
|
Oct. 27 |
No Lecture |
Oct. 29 |
Midterm In Class!
|
Oct. 31 (Boo!) |
Lecture 15
Pattern Matching
|
7
Reading: 2.2
|
Nov. 3 |
Introduction to Context Free Languages
|
Nov. 5 |
Lecture 17
Ambiguity in CFGs
|
Nov. 7 |
Lecture 18
Chomsky Normal Form
|
8
Reading: 2.3
|
Nov. 10 |
Lecture 19
Pushdown Automata
Homework 5 due |
Nov. 12 |
Lecture 20
Pushdown Automata
|
Nov. 14 |
Lecture 21
Closure Properties of CFLs
|
9
Reading: 3.1 and 3.2
|
Nov. 17 |
Lecture 22
CFG and PDAs
|
Nov. 19 |
Lecture 23
Pumping lemma for CFLs
|
Nov. 21 |
Lecture 24
Pumping lemma for CFLs
Homework 6 due
|
10
Reading: 4.1 and 4.2
|
Nov. 24 |
Lecture 25
Cocke-Younger-Kasam
| Nov. 26 |
Lecture 26
Turing Machines
|
Nov. 28 |
Thanksgiving Holiday
|
10
Reading: 4.2
|
Dec. 1 |
Lecture 27
Decidability
|
Dec. 3 |
Lecture 28
The Halting Problem
|
Dec. 5 |
Final Review
Homework 7 due |
11
|
Dec. 8 |
Final Exam
2:30-4:20pm in EE 037
|
|
|
|
|
|
CSE Home 
