CS 311
Fall 2008
Audrey St. John

CS 311 Fall 2008 Schedule

Under Construction



Lecture notes may not be posted for all the classes. A handout available before the actual lecture is only tentative and may be changed at any time by the instructor. Handouts are not meant as a substitute for class attendance, but as guidelines for the topics covered in class.

Class #

Date
Notes

Topic
Assignment
1

F 9/5
Notes 1

Overview and Intro to DFAs

2

M 9/8
Notes 2

Regular operations
Assignment 1
3

W 9/10
Notes 3

NFAs

4

M 9/15
Notes 4

Equivalence of NFAs and DFAs
Assignment 2
5

W 9/17
Notes 5

Closure under regular operations

6

M 9/22
Notes 6

Regular expressions

M

W 9/24
 

Mountain Day - no class!
7

M 9/29
Notes 7

Regular expressions <=> regular languages
Assignment 3
8

W 10/1
Notes 8

Nonregular languages

9

M 10/6
Notes 9

Context-free grammars

E

W 10/8


Exam I
Solutions

10/11 - 10/14

Mid-semester break

10

W 10/15
Notes 10

Pushdown automata
11

M 10/20
Notes 11
Context-free => pushdown
 
12

W 10/22
Notes 12

Pushdown => context-free
Assignment 5
13

M 10/27
Notes 13

Turing machines
14

W 10/29
Notes 14

More Turing machines
Assignment 6
15

M 11/3
Notes 15

Algorithms
16

W 11/5
Notes 16

Decidable languages
Assignment 7
17

M 11/10
Notes 17

The Halting Problem
18

W 11/12
Notes 18

Reducibility
E2

M 11/17


Exam II
Solutions

19

W 11/19
Notes 19

Computable functions, reduction
Assignment 8
20

M 11/24
Notes 20

Measuring time complexity


11/26 - 11/30

Thanksgiving recess

21

M 12/1
Notes 21

P and NP
Assignment 9
22

W 12/3
Notes 22

NP-completeness

23

M 12/8
Notes 23

More NP-completeness
24

W 12/10
Notes 24

Final exam review.