CSE 547T Introduction to Formal Languages and Automata, Fall 2015

Tuesday and Thursday, 1:00-2:30 PM, Lopata Hall 101.

Final exam: Tuesday, December 15, 2015 1:00-3:00 PM, Lopata Hall 101.

Instructor

Brendan Juba
Office Hours:   Wednesday 5-6 PM, Bryan 522
Email:   first initial last name at wustl

Course Staff

Ruth Chen
Office Hours:   Thursday 4-5:30 PM, Urbauer 114

Roger Iyengar
Office Hours:   Tuesday 5:30-6:30 PM, Urbauer 114

Kaci Karlsson
Office Hours:   Monday 12-1 PM, Urbauer 114

Description

An introduction to the theory of computation, with emphasis on the relationship between formal models of computation and the computational problems solvable by those models. Specifically, this course covers finite automata and regular languages; Turing machines and computability; and basic measures of computational complexity and the corresponding complexity classes

Pre-requisites

Formally, CSE 240. (Math 310 is also acceptable.) Informally, this class will demand "mathematical maturity." This means that you should be comfortable reading and producing mathematical arguments, i.e., "proofs." A key part of this course will be coming up with and clearly presenting such proofs on the homework.

Textbook

We will use Introduction to the Theory of Computation by Michael Sipser. Either the second or third edition of the book will do (but not the first edition). Readings and homework problems will be assigned from the text.

Piazza

All students enrolled in the class are automatically signed up for Piazza, a website for facilitating discussions about classes. Please register as soon as you receive the e-mail, if you haven't already. All questions that are not of a personal nature should be posted to Piazza. You will find it helpful when your classmates have already asked a question for you, with an answer already posted. But, in order to sustain this, you must ask your questions to Piazza as well, and so we will strictly maintain this policy.

The Piazza page for this class is located at piazza.com/wustl/fall2015/cse547t/home

Homework, Exams, and Grading

Tentatively, there will be seven homework assignments, a midterm exam, and a final exam. The homeworks will be worth 40% of the grade, the midterm will be worth 25%, and the final exam will be worth 35%. The final exam is cumulative, but emphasizes the second half of the course.

Homework is an essential component of this course and lectures will sometimes refer to the results of homework problems. We will be using electronic homework submissions this semester: your homeworks will need to be electronically typeset and submitted via Blackboard. Please see the E-Homework Guide for details on how to submit your homework assignments and retrieve your graded assignments. The course calendar contains a tentative schedule for the homework assignments. Homework will be due at the beginning of lecture on the indicated day. You have a total of 4 late days per semester at no grade penalty. At most two days late may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not yours) score per late day. (Note that days on the weekend still count as late days!)

The homework problems will be graded on a three point scale, "check+," "check," and "check-." These roughly mean:
Check+: complete and correct.
Check  : on the right track, but missing some essential detail(s) or part of the idea.
Check- : missed the idea.
Zero points will be awarded if no attempt has been made at the problem, or if the submission is found to be in violation of the academic integrity policy (below).

Collaboration and Academic Integrity policy

On homeworks, students are highly encouraged to collaborate, and are permitted to use any sources whatsoever so long as these are documented properly on each problem (including a full reference to the source) and the text is original -- verbatim copying of a source is not permitted. Students will be required to produce and submit their own, individual writeups.

Disability Resources

Students with disabilities or suspected disabilities are strongly encouraged to both bring any additional considerations to the attention of the instructors and make full use of the University's Disability Resource Center (http://disability.wustl.edu).

Course Website

An up-to-date version of this document appears on the web at http://www.cse.wustl.edu/~bjuba/cse547t/f15.

Calendar

The schedule of lecture topics and assignments may be subject to change as the semester progresses.
MondayTuesday WednesdayThursday Friday
Aug 24
Aug 25

L1:  Finite Automata
S (Sipser) 1.1
Assigned:  Review Chapter 0
Aug 26
Aug 27

L2:  Nondeterminism
Finish S 1.1, start S 1.2
Aug 28
Aug 31
Sept 01

L3:  Regular Languages are closed under the Regular Operations
S 1.2
Assigned:  Homework 1
Sept 02
Sept 03

L4:  Regular Expressions
S 1.3
Sept 04
Sept 07
Holiday
Sept 08

L5:  Converting Finite Automata to Regular Expressions
finish S 1.3, start 1.4
Sept 09
Sept 10

L6:  Pumping Lemma
S 1.4
Due:  Homework 1
Assigned:  Homework 2
Sept 11
Sept 14
Sept 15

L7:  Minimum size DFAs
S Problems 1.51, 1.52 (2e/3e), and 7.40(2e)/7.42 (3e); (1.47, 1.48, and 7.25, i3e)
Sept 16
Sept 17

L8:  DFA minimization; Turing Machines
S Problem 7.40/7.42/7.25, start 3.1
No Office Hours
Sept 18
Sept 21
Sept 22

L9:  Robustness of Turing Machines
S 3.1, 3.3, start 3.2
Due:  Homework 2
Assigned:  Homework 3
Sept 23
Sept 24

L10:  Multi-tape Turing Machines; Decidability
S 3.2, finish 3.3, start 4.1
Sept 25
Sept 28
Sept 29

L11:  Undecidability and Reductions
finish S 4.1, 4.2, start 5.1
Sept 30

No Office Hours
Oct 01

Midterm Review
Due:  Homework 3
Oct 02
Oct 05
Oct 06

Midterm Exam
(in class)
Oct 07
Oct 08

L12:  Post Correspondence Problem
S 5.1, 5.2
Oct 09
Oct 12
Oct 13

L13:  Mapping Reducibility
S finish 5.2, 5.3
Assigned:  Homework 4
Oct 14
Oct 15

L14:  Unrecognizability and Co-recognizability
S 5.3 (+ finish 4.2), start 6.1
Oct 16
Holiday
Oct 19
Oct 20

L15:  Self-reference and Undecidability in Logic and Mathematics
S 6.1, 6.2, problem 6.9 (2e/3e)/6.25 (i3e)
Oct 21

No Office Hours
Oct 22

L16:  Time Complexity
S 7.1
No Office Hours
Due:  Homework 4
Assigned:  Homework 5
Oct 23
Oct 26
Oct 27

L17:  Polynomial Time
S 7.2
Oct 28
Oct 29

L18:  NP
S 7.3
Oct 30
Nov 02
Nov 03

L19:  Nondeterministic Turing Machines
finish S 7.1/7.3, start 9.3
Due:  Homework 5
Assigned:  Homework 6
Nov 04
Nov 05

L20:  Circuit Complexity
S 9.3, start 7.4
Nov 06
Nov 09
Nov 10

L21:  NP-completeness
S 7.4 (finish 9.3)
Nov 11
Nov 12

L22:  Ubiquity of NP-completeness
S 7.5
Due:  Homework 6
Assigned:  Homework 7
Nov 14
Nov 16
Nov 17

L23:  Space Complexity
(finish S 7.5) S 8.0, 8.2
Nov 18
Nov 19

L24:  PSPACE-completeness
S 8.1, start 8.3
Nov 20
Nov 23
Nov 24

L25:  PSPACE and Games
S 8.3
Due:  Homework 7
Practice problems
Nov 25

Thanksgiving travel day
Nov 26

Thanksgiving
Nov 27
Nov 30
Dec 01

L26:  Resource Hierarchies
S 9.1
Dec 02
Dec 03

L27: Limitations of Diagonalization
S 9.2
Dec 04

Lecture notes

For your convenience, I'm posting my handwritten lecture notes. (Notes for all of the lectures are now posted.) Unfortunately, one line at the end of each page is considered "beyond the border of the page" and does not display in a browser (although it is present in the source files). The files are provided as-is in a strange format, and there is not much I can do about them. The correspondence to the actual topics covered in lecture is also only approximate.

L1 L2-3 L4-5 L6 L7 L8 L9 L10 L11 L12 L13 L14 L15 L16 L17 L18 L19 L20 L21 L22 L23 L24 L25