| Wk |
Day |
Date |
Topic | Resources | Events |
|
| 1 | Tue | Jan 09 | Introduction to course
Mathematics | Your brains
Course website
JFlap
JFlap Tutorial | Pretest |
|
|
| Thu | Jan 11 | Mathematics
Induction Proofs | Chapter 0
Proofs Notes
Proof Examples
Induction Proofs | |
|
| 2 | Tue | Jan 16 | Finite Automata | Chapter 1.1
Finite State Machines Notes |
HW 1 due |
|
|
| Thu | Jan 18 | DFAs | |
Problems 1.1 |
|
| 3 | Tue | Jan 23 | Nondeterministic Finite Automata | Chapter 1.2 |
HW 2 due |
|
|
| Thu | Jan 25 | NFAs | |
Problems 1.2 |
|
| 4 | Tue | Jan 30 | Regular Expressions | Chapter 1.3 |
HW 3 due |
|
|
| Thu | Feb 01 | Regular Expressions | |
Problems 1.3 |
|
| 5 | Tue | Feb 06 | Nonregular Languages | Chapter 1.4 |
HW 4 due |
|
|
| Thu | Feb 08 | Nonregular languages | |
Problems 1.4 |
|
| 6 | Tue | Feb 13 | Winter Break | | No Class |
|
|
| Thu | Feb 15 | Context-Free Grammar | Chapter 2.1
C++ Grammar
Java Grammar
A simple grammar |
HW 5 due |
|
| 7 | Tue | Feb 20 | Pushdown Automata
Non-Context-Free Languages | Chapter 2.2 |
HW 6 due |
|
|
| Thu | Feb 22 | Context-Free Grammar
Pushdown Automata
Non-Context-Free Languages | |
Problems 2.1-2.2 |
|
| 8 | Tue | Feb 27 | Non-Context-Free Languages | Chapter 2.3 |
HW 7 due
|
|
|
| Thu | Mar 01 | Pushdown Automata
Non-Context-Free Languages | |
Problems 2.2-2.3 |
|
| 9 | Tue | Mar 06 | Chapters 1-2 | |
HW 8 due
Review |
|
|
| Thu | Mar 08 | Turing Machines | Chapter 3.1
Turing Machine stuff (See picture near middle)
Turing Machine Cartoon
Turing Machine Applet
Simple Math Turing Machine | |
|
| 10 | Tue | Mar 13 | Chapters 1-2 | Pencil
Paper
Definition/Results sheet | Midterm Exam |
|
|
| Thu | Mar 15 | Turing Machine Variants
Algorithms
Homework 10 | Chapter 3.2-3.3 | |
|
|
Spring Break Week |
|
| 11 | Tue | Mar 27 | Turing Machines | Chapter 3.1-3.3 | Problems 3.1-3.3 |
|
|
| Thu | Mar 29 | Decidable Languages | Chapter 4.1
Decidability Notes |
HW 9 due |
|
| 12 | Tue | Apr 03 | The Halting Problem | Chapter 4.2
Halting Problem Notes |
HW 10 due |
|
|
| Thu | Apr 05 | Decidability | | Problems 4.1-4.2 |
|
| 13 | Tue | Apr 10 | Reducibility | Chapter 5.1-5.3
Reducibility Notes |
HW 11 due |
|
|
| Thu | Apr 12 | Complexity | Chapter 7.1-7.2
Complexity Notes |
HW 12 due |
|
| 14 | Tue | Apr 17 | NP
NP-Complete | Chapter 7.3-7.4
NP-Complete Notes |
HW 13 due |
|
|
| Thu | Apr 19 | NP-Complete | Chapter 7.4-7.5 | |
|
| 15 | Tue | Apr 24 | Complexity | | Problems 5.1-5.3
Problems 7.1-7.5 |
|
|
| Thu | Apr 26 | Final Exam Review
Semester Wrap-up | |
HW 14 due |
|
| 16 | Tue | May 01 | The whole book | Pen or Pencil
Paper
Definition/Results Sheet
Brain | Final Exam @ 10:30am
Homework 15 due |