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

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

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