Comp 375: Theory of Computation

Spring 2021

Schedule

This schedule is just an attempt to give you an idea of what's coming. I will probably update it as we cover topics.

WEEK DAY ANNOUNCEMENTS TOPIC & READING LABS     
1

Feb 03

  

Introduction

  • Sipser Chapter 0

W1

Feb 05

  
2

Feb 08

  

Deterministic Finite Automaton

  • Sipser Chapter 1.1

W2

Feb 10

Drop/add ends (Feb 11)

Feb 12

  
3

Feb 15

  

Nondeterministic Finite Automaton

  • Sipser Chapter 1.2

W3

Feb 17

  

Feb 19

  
4

Feb 22

  

Regular Expression

  • Sipser Chapter 1.3

W4

Feb 24

  

Feb 26

  
5

Mar 01

  

Nonregular Languages

  • Sipser Chapter 1.4

W5

Mar 03

  

Mar 05

  
6

Mar 08

  

Context-Free Grammars

  • Sipser Chapter 2.1

W6

Mar 10

Break

Mar 12

  

More CFGs (continued)
7

Mar 15

Test 1

Pushdown Automaton

  • Sipser Chapter 2.2

W7

Mar 17

  

Mar 19

  
8

Mar 22

  

Non-Context-Free Languages

  • Sipser Chapter 2.3

W8

Mar 24

  

Mar 26

Withdraw Deadline
9

Mar 29

Advisement Week

Turing Machines

  • Sipser Chapter 3.1

W9

Mar 31

  

Apr 02

  
10

Apr 05

  

TM Variants and Algorithms

  • Sipser Chapter 3.2 and 3.3

W10

Apr 07

  

Apr 09

Registration Deadline for F19
11

Apr 12

  

Decidable Languages

  • Sipser Chapter 4.1

W11

Apr 14

  

Apr 16

  
12

Apr 19

Test 2

Halting Problem and Undecidable problems

  • Sipser Chapter 4.2 and 5.1

W12

Apr 21

  

Apr 23

Pass/Fail Deadline
13

Apr 26

  

Reductions

  • Sipser Chapter 5.3

W13

Apr 28

  

Apr 30

Break
14

May 03

  

Advanced Topics to Taste and Catching Up

W14

May 05

  

May 07

  

Review

 

May 10

Final Exams Start

May 15

Final Exams End