# CS46: Theory of Computation

Spring 2018

## Announcements

• Lab 09 is posted and due 2 May 2018.
• Please create an account through iClicker, register your remote, and add CS46 Theory of Computation as a course. Search for Danner.
 WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS 1 Jan 23 Introduction Reading: Chapter 0 Notes Jan 25 2 Jan 30 Deterministic finite automata regular langauges Nondeterminism regular expressions Reading: Chapter 1.1-1.3 Feb 01 Drop/add ends (Feb 02) 3 Feb 06 Non Regular languages Reading: Chapter 1.4 Feb 08 4 Feb 13 Context-free grammars Pushdown automata Reading: Chapter 2.1-2.2 Feb 15 5 Feb 20 Non Context-free Languages * Reading: Chapter 2.3 Feb 22 6 Feb 27 Turing Machine Intro * Reading: Chapter 3.1-3.2 Midterm Review Mar 01 Final Exam Schedule Released 7 Mar 06 Computability and the Church Turing Thesis * Reading: Chapter 3.3 Midterm Mar 08 Test 1 Mar 13 Spring Break Mar 15 8 Mar 20 Decidability and Undecidability * Reading: Chapter 4 Mar 22 9 Mar 27 Reductions * Reading: Chapter 5 (skip 5.2) Mar 29 CR/NC/W Deadline (Mar 30) 10 Apr 03 Time complexity, the class $P$ * Reading: Chapter 7.1-7.3 Apr 05 11 Apr 10 The class $NP$, $NP$-completeness * Reading: Chapter 7.4-7.5 Midterm Review Apr 12 12 Apr 17 $SAT$ is $NP$-Complete Midterm Apr 19 Test 2 13 Apr 24 Other $NP$-Complete problems Apr 26 14 May 01 Wrapup Review May 03 May 10 Final Exam 2pm-5pm Sci 105