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.

Office Hours: Wednesday 5-6 PM, Bryan 522

Email:

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

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

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).

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 |

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