CS 310 Schedule
|
Date
|
Topic
|
Notes
|
Assignments
|
| Aug 27 | Introduction, What is Computation?, Sets (chapter 0) | PDF |
Computing
is a natural science |
| Aug 29 |
Proofs, Strings, Languages | Hmwk#1: p25: 0.1 (a-c), 0.2 (a-f), 0.3, 0.4, 0.5, 0.6, 0.7, 0.10,0.11,0.12 Prove by Induction: For any natural number n: 1+3+5+...+ (2n-1) = n^2 DUE Sep 5 (typed!) |
|
| Aug 31 |
Finite Automata & Languages
(chapter 1) |
|
|
| Sep 03 | NO CLASSES -- Labor Day |
|
|
| Sep 05 | Finite Automata & Languages (chapter 1) | Homework DUE |
|
| Sep 07 |
Regular Languages and NFAs | PDF |
|
| Sep 10 |
DFA/NFA Practice |
PDF |
|
| Sep 12 | NFA/DFA Equivalence & JFLAP | PDF JFLAP |
Homework JFLAP ERROR Testing a FA Testing with multiple strings Batch Testing FAs |
| Sep 14 | NFA/DFA Equivalence | PDF |
|
| Sep 17 |
Regular Expressions | PDF |
JFLAP Homework DUE Hmwk #3 |
| Sep 19 |
Regular Expressions | ||
| Sep 21 |
Regular Expressions / GNFA | GNFA |
|
| Sep 24 |
Pumping Lemma | PDF |
Hmwk #3 DUE Hmwk#4 |
| Sep 26 | Pumping Lemma |
Exam
Review |
|
| Sep 28 |
Review | Hmwk #4 DUE |
|
| Oct 01 | Exam One |
|
|
| Oct 03 | Mealy / Moore Machines | Mealy/Moore Mealy |
|
| Oct 05 | NO CLASSES -- Fall Break |
|
|
| Oct 08 |
Context Free Languages / Context Free Grammars | PDF |
|
| Oct 10 |
|
Hmwk#5 | |
| Oct 12 | CNF / Pushdown Automata | ||
| Oct 15 |
|
|
Natural Languages 1, 2 |
| Oct 17 |
Examples | Hmwk#6 Hmwk#5 DUE |
|
| Oct 19 |
PDA to CFG |
||
| Oct 22 |
Non-CFL / Pumping Lemma | |
|
| Oct 24 | |||
| Oct 26 | LL(1) Parsing (Dragon Book) |
PDF |
Hmwk #6 DUE Hmwk#7 |
| Oct 29 |
LL(1) Parsing |
PDF |
|
| Oct 31 |
Pumping Lemma Review | LL(1) Parsing | PDF |
|
| Nov 02 |
LL(1) Parsing | ||
| Nov 05 | Turing Machines | PDF |
Exam Review |
| Nov 07 |
PDF |
||
| Nov 09 | Exam Two |
|
|
| Nov 12 | TM Variations | PDF |
|
| Nov 14 | TM Variations | Hmwk#8 TM in JFLAP Turing |
|
| Nov 16 | Decidability | PDF |
Prime Density Minimal Primes #1, #2, ref |
| Nov 19 | Halting Problem | more | |
| Nov 21 | NO CLASSES -- Thanksgiving Break | |
|
| Nov 23 | NO CLASSES -- Thanksgiving Break | |
|
| Nov 26 | Reducibility / Time Complexity | PDF Reducibility PDF Complexity |
Hmwk#9 |
| Nov 28 |
Class of P Languages |
PDF |
Final Review |
| Nov 30 |
P vs NP |
PDF |
Minesweeper is NP-Complete #1 #2 |
| Dec 03 | Review | ||
| Dec 11 |
FINAL 8:30 - 11:00 AM |
