Computer Science 416/685: Computability Theory
Lehman College, City University of New York
Fall 2016

Instructor:	Prof. Katherine St. John
E-mail:	katherine.stjohn at lehman.cuny.edu
Office:	Gillet 137D
Office Hours:	Tuesdays, Thursdays 9:30-11am and by appointment.
Class Hours:	Tuesdays, Thursdays 11am-12:40pm.

Announcements:

• Who should take this course?
  • This course is aimed at undergraduate and masters students who are planning doctoral studies in computer science, applied mathematics, or mathematics.
  • It is required by almost all Ph.D. programs in computer science (either the course itself or as prerequisite to the doctoral level course).
  • Many programs will allow you to "make up" the course during your first year of doctoral study, but it is still worth taking this course earlier since the material appears on the GRE as well as job interviews.
  • The material is a mixture of computer science and mathematics, so, will be of interest to computer science and applied mathematics students considering doctoral study and mathematics students who are minoring in computer science.
• What is computability theory?  Computability theory studies such questions as "can I find an algorithm that will solve this problem?" and "which problem is harder to compute?" in a rigorous fashion. We will cover:
  • automata and languages (regular languages, finite state automata, nondeterminism, regular expressions, context-free languages and grammars, and pushdown automata),
  • computability theory (Turing machines, decidability, and reducibility),
  • as well as time and space complexity and intractability.
• Should I sign up for undergraduate or graduate credit?  This course is being taught both as an undergraduate and masters course.  While the lectures will be the same for the two courses, the assignments, reading, and exams will be at a higher level for masters students.  If you are a masters students, you must take the course for graduate credit.

Useful Links:

• Syllabus
• Book's webpage
• Finite State Machine simulators
• Turing Machine examples
• Turing Machine Simulator

Outline:

Date:	Topics:	Handouts:	Reading:	Problem Sets:
#1 25 August	First Day Details, Topics Overview, Finite State Automata	Syllabus, Class Work 1	Academic Integrity Policy, Section 1.1	#1: Finite Automata
#2 30 August	Examples (student presentations), Formal definition of (deterministic) finite automata (DFA), Regular Operators	Class Work 2
31 August	Last day to drop without "WD" grade
#3 1 September	Nondeterministic finite automata (NFA), Equivalence of NFA and DFA	Class Work 3	Section 1.2	#2: Nondeterminism
#4 6 September	Examples and Closure under Regular Operators, Student Presentations	Class Work 4
#5 8 September	Regular Expressions: definition and equivalence with finite automata	Class Work 5	Section 1.3	#3: Regular Expressions
#6 13 September	More on Regular Expressions, Student Presentations	Class Work 6
14 September	Last day to drop with "WD" grade
#7 15 September	The Pumping Lemma, Student Presentations	Class Work 7	Section 1.4	#4: Nonregular Languages
#8 20 September	Nonregular Languages	Class Work 8
#9 22 September	Context Free Languages, Student Presentations	Class Work 9	Section 2.1	#5: Context-Free Languages
#10 27 September	Regular Languages Review	Class Work 10, Exam 1 Information	Chapter 1
Exam 1 29 September	Midterm Examination 1
4 October	No classes scheduled.
6 October	No class: Classes follow a Monday schedule
11 October	No classes scheduled.
#11 13 October	Context-free Grammars, Chomsky Normal Form	Class Work 11	Section 2.1
#12 Friday, 14 October	Pushdown Automata (PDA), Equivalence with Context-free grammars, Non-context-free languages	Class Work 12	Section 2.2	#6: Pushdown Automata
#13 18 October	Non-context-free languages, The Pumping Lemma for context-free languages, Student Presentations	Class Work 13
#14 20 October	More on Context-free Languages, Student Presentations	Class Work 14	Section 2.3	#7: Non-context-free Languages
#15 25 October	Student Presentations, Introduction to Turing Machines (TM)	Class Work 15
#16 27 October	Computing with Turing Machines (TM)	Class Work 16	Chapter 3	#8: Turing Machines
#17 1 November	Variations on TM, Equivalence with other models, Student Presentations	Class Work 17
#18 3 November	More on TM, Review	Class Work 18, Exam 2 Information
Exam 2 8 November	Midterm Examination 2
10 November	Last day to drop with "W" grade
#19 10 November	Decidable languages	Class Work 19	Section 4.1	#9: Decidable Languages
#20 15 November	More on Decidability, Student Presentations	Class Work 20
#21 17 November	The Halting Problem, the Diagonalization Method	Class Work 21	Section 4.2	#10: The Halting Problem
#22 22 November	Undecidability, Student Presentations	Class Work 22
24-27 November	Thanksgiving Holiday: No Classes
#23 29 November	Big-oh and Small-oh Notation, Analyzing Algorithms	Class Work 23	Section 7.1	#11: Measuring Complexity
#24 1 December	Complexity under Different Models, Theta and Omega Notation, Student Presentations	Class Work 24
#25 6 December	Polynomial Time (P) and Nondeterministic Polynomial Time (NP) Classes	Class Work 25	Sections 7.2-7.3	#12: P and NP
#26 8 December	More on Algorithm Classes, Student Presentations	Final Exam Information
13 December	Reading Day (no class) Optional Review during 11am - 12:40pm, Room TBA
11am-1pm Thursday, 15 December	Final Examination (required)

(Last updated: 17 November 2016)