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.
  • Log into Piazza.

Anonymous Feedback

I value any and all feedback. Please feel free to stop by my office, email me at adanner@cs or submit anonymous feedback. Since the last feedback form is anonymous, I cannot reply to any requests directly.

Schedule

WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS     
1

Jan 23

 

Introduction

  • Reading: Chapter 0
  • Notes

Lab 1
Practice

Jan 25

 
2

Jan 30

 

Deterministic finite automata

  • regular langauges
  • Nondeterminism
  • regular expressions
  • Reading: Chapter 1.1-1.3

Lab 2
Practice

Feb 01

Drop/add ends (Feb 02)

3

Feb 06

 

Non Regular languages

Reading: Chapter 1.4

Lab 3
Practice

Feb 08

 
4

Feb 13

 

Context-free grammars

  • Pushdown automata
  • Reading: Chapter 2.1-2.2

Lab 4
Practice

Feb 15

 
5

Feb 20

 

Non Context-free Languages
* Reading: Chapter 2.3

Lab 5
Practice

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

Lab 6
Practice

Mar 22

 
9

Mar 27

 

Reductions
* Reading: Chapter 5 (skip 5.2)

Lab 7
Practice

Mar 29

CR/NC/W Deadline (Mar 30)

10

Apr 03

 

Time complexity, the class $P$
* Reading: Chapter 7.1-7.3

Lab 8
Practice

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

Lab 9
Practice

Apr 26

 
14

May 01

 

Wrapup

Review

May 03

 
 

May 10

Final Exam 2pm-5pm Sci 105