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