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:

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.

Monday	Tuesday	Wednesday	Thursday	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