CSE 547T Course Calendar, Spring 2017


This is a tentative outline of lecture topics and assignment dates for the semester. The dates and topics on this syllabus (especially for the second half of the course) are subject to change, depending on how quickly we cover the material.

Readings are from from Sipser's Introduction to the Theory of Computation, 3rd Ed.

Date Lecture Topic Readings Homework Due Homework Assigned
Wed
Jan 18
Intro; Strings and Languages Sec 0.2 Homework 0 (optional)
Mon
Jan 23
Deterministic Finite Automata Sec 1.1
Wed
Jan 25
Nondeterministic Finite Automata Sec 1.2 Homework 0 (optional) Homework 1
Mon
Jan 30
NFA-DFA Equivalence Sec 1.2
Wed
Feb 1
NFAs with Null Transitions Sec 1.2
Mon
Feb 6
Regular Expressions; Kleene's Theorem Sec 1.3
Wed
Feb 8
Finish Kleene's Theorem; Closure Properties of RLs Sec 1.2, 1.3
Mon
Feb 13
Proving Languages Non-Regular; Pumping Lemma Sec 1.4 Homework 1 Homework 2
Wed
Feb 15
Non-Uniqueness of DFAs; Myhill-Nerode Thm
Mon
Feb 20
DFA Minimization
Wed
Feb 22
Finish Up RLs
Mon
Feb 27
Introduction to Turing Machines Sec 3.1
Wed
Mar 1
Simulating Extensions to TMs Sec 3.2 Homework 2
Mon
Mar 6
Exam 1
Wed
Mar 8
RE and Recursive Languages Sec 4.1, 4.2
Mar 13-17 Spring Break
Mon
Mar 20
Universal TMs and Existence of non-RE Languages Sec 4.2 Homework 3
Wed
Mar 22
Undecidable Problems on TMs Sec 5.1
Mon
Mar 27
Proving a Language Nonrecursive: Reduction Arguments Sec 5.1
Wed
Mar 29
The Post Correspondence Problem Sec 5.2
Mon
Apr 3
Time Complexity of TMs Sec 7.1
Wed
Apr 5
The Classes P and NP Sec 7.2, 7.3 Homework 3 Homework 4
Mon
Apr 10
instructor out -- no class
Wed
Apr 12
NP-Completeness: Cook's Theorem Sec 7.4
Mon
Apr 17
NP-Completeness: Reductions Sec 7.4, 7.5
Wed
Apr 19
Space Complexity Sec 8.1
Mon
Apr 24
The Class PSPACE Sec 8.2 Homework 4
Wed
Apr 26
PSPACE-Completeness Sec 8.3
Fri
May 5
6-8 PM
Exam 2

CSE 547T
Last Update: 1/31/2017