CS 310 Schedule
|
Date
|
Topic
|
Notes
|
Assignments
|
| Aug 25 | Introduction, What is Computation?, Sets (chapter 0) | PDF |
|
| Aug 27 |
Proofs, Strings, Languages |
Hmwk#1 DUE Sep 5 (typed!) |
|
| Aug 29 |
Finite Automata & Languages
(chapter 1) |
|
|
| Sep 01 | NO
CLASSES -- Labor Day |
|
|
| Sep 03 | Finite Automata & Languages (chapter 1) |
|
|
| Sep 05 |
Regular Languages and NFAs | PDF |
Homework DUE |
| Sep 08 |
DFA/NFA Practice |
PDF |
|
| Sep 10 | NFA/DFA Equivalence & JFLAP | PDF JFLAP |
Homework JFLAP ERROR Testing a FA Testing with multiple strings Batch Testing FAs |
| Sep 12 | NFA/DFA Equivalence & Practice | PDF |
|
| Sep 15 |
Regular Expressions | PDF |
|
| Sep 17 |
Regular Expressions | JFLAP Homework DUE Hmwk #3 |
|
| Sep 19 |
Regular Expressions / GNFA | GNFA |
|
| Sep 22 |
Regular
Expressions / GNFA |
Hmwk
#3 DUE Hmwk#4 Exam Review |
|
| Sep 24 | Pumping Lemma |
PDF |
Notes
on Hmwk3 |
| Sep 26 |
Pumping Lemma / Review |
Hmwk #4 DUE |
|
| Sep 29 | Exam One |
|
|
| Oct 01 | Pumping Lemma Practice | |
|
| Oct 03 | NO
CLASSES -- Fall Break |
|
|
| Oct 06 |
Context Free Languages / Context Free Grammars | PDF |
|
| Oct 08 | |
|
|
| Oct 10 | |
||
| Oct 13 |
CNF / Pushdown Automata | |
Hmwk#5 Natural Languages Evidence against the CFGness Complexity of NL |
| Oct 15 |
Examples | |
|
| Oct 17 |
PDA to CFG |
PDF |
|
| Oct 20 |
PDA to CFG | PDF |
Hmwk#5 DUE |
| Oct 22 | PDA to CFG | PDF |
Hmwk#6 |
| Oct 24 | |
||
| Oct 27 |
Non-CFL / Pumping Lemma | ||
| Oct 29 |
Non-CFL / Pumping Lemma | ||
| Oct 31 |
Pumping Lemma Review | Hmwk#6 DUE | |
| Nov 03 | Turing Machines | PDF |
Exam
Review |
| Nov 05 |
|||
| Nov 07 | Exam Two |
|
|
| Nov 10 | TM Variations | PDF |
|
| Nov 12 | TM Variations | Hmwk#8 TM in JFLAP Turing |
|
| Nov 14 | TM Variations | ||
| Nov 17 | Decidability/ Halting Problem | PDF |
Prime
Density Minimal Primes #1, #2, ref |
| Nov 19 | Halting Problem | Reducibility | Complexity | PDF Complexity |
more
on Halting |
| Nov 21 | Complexity | Class of P Languages |
Hmwk#9 Final Review |
|
| Nov 24 | P vs NP | Minesweeper is NP-Complete #1 #2 | |
|
Nov 26 |
NO CLASSES -- Thanksgiving Break |
|
|
|
Nov 28 |
NO CLASSES -- Thanksgiving Break | ||
| Dec 01 | Review | ||
| Dec 05 FRIDAY |
FINAL
3:00 - 5:30pm |
