Instructor
| VIU Profile: | Dr Russell Campbell |
| Email: | Russell.Campbell [at] viu [dot] ca |
| Office: | Nanaimo Campus, Building 315, Room 218 |
Email me to set up a time for discussion on Zoom if needed.
Schedule
The following plan for weekly topics, assignments, and labs is only a draft and is subject to change.
| Week | Topic |
|---|---|
| Jan 7 | Ch 0: Sets, Sequences, Functions, Graphs |
| Jan 11–15 | Ch 0: Strings and Languages; Ch 1.1: Finite Automata |
| Jan 18–22 | Ch 1.2: Nondeterminism; Ch 1.3: Regular Expressions |
| Jan 25–Jan 29 | Ch 1.4: Nonregular Languages |
| Feb 1–5 | Midterm 1; Ch 2.1: Context-Free Languages |
| Feb 8–12 | Ch 2.2: Pushdown Automata |
| Feb 15–19 | (study days) |
| Feb 22–26 | Ch 2.3: Non-Context-Free Languages |
| Mar 1–5 | Ch 3.1: Turing Machines; Ch 3.3: The Definition of Algorithm |
| Mar 8–12 | Ch 4.1: Decidable Languages |
| Mar 15–19 | Midterm 2; Ch 4.2: Undecidability |
| Mar 22–26 | Ch 5.1: Undecidable Problems from Language Theory |
| Mar 29–Apr 2 | Ch 5.3: Mapping Reducibility; Ch 7.1: Measuring Complexity |
| Apr 5–9 | (no lectures) |
| Apr 12–16 | Ch 7.2--7.4: P, NP, NP-completeness |
Midterms
- Feb 2–Feb 4 Midterm 1
- Mar 16–Mar 18 Midterm 2
Assignments
- Jan 11–Jan 22 Assignment 1
- Jan 23–Feb 2 Assignment 2
- Feb 8–Feb 21 Assignment 3
- Feb 22–Mar 5 Assignment 4
- Mar 22–Apr 1 Assignment 5
- Apr 3–Apr 16 Assignment 6
Labs
There will be no lab work; however, scheduled time for labs will be used as synchronous meeting times to discuss coursework.