Students,
All lectures and supplementary talks will be recorded and broadcast via YouTube Live through user @cd-public, for which there is a course specific playlist.
- General: https://www.youtube.com/@cd-public/streams
- Course: https://www.youtube.com/watch?v=ExpLC4r4H9M&list=PLu3KAnn4RkATkXZsQuk6Fj7p3iqn-iYj1
All course material will be hosted via GitHub pages at the following url, for which this is a course specific page.
- General: https://cd-public.github.io/courses/
- Course: https://cd-public.github.io/compute/index.html
In addition to office hours by appointment, as a collaboration and student support tool I will host a course Discord. Discord is not required, but I will use it a lot.
- Link not public.
All technologies used in the course are available free and open source. There is no textbook, but supplemental options for texts will be provided.
- Optional Text: Sipser, Michael. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012. ISBN: 9781133187790
There is a strong trend in academia toward learning management systems like Brightspace and toward maintaining student visible gradebooks, which have strong benefits for other courses but not, I think, for mine. I note that:
- I do not use LMS systems, which I find difficult to integrate with the technology stacks that achieve core instructional goals for courses within the computational sciences.
- I do not use a student visible gradebook because I use ungrading, which I have found to be associated with stronger achievement from students in demanding courses.
Reach out via email or Discord if you want a grade check or cannot find some course materials.
Best,
-c
Study of abstract models of computation, unsolvability, complexity theory, formal grammars and parsing, and other advanced topics in theoretical computer science.
January 13 - 22, 2025
| Week | Date | Talk | Code |
|---|---|---|---|
| 0x0 | 13 Jan | Quarto .md | .qmd |
| 0x1 | 20 Jan | Quarto Pages | .qmd |
30 Jan - 02 Feb, 2025
| Fri | Sat | Sun | |
|---|---|---|---|
| 08:30 AM | Aims of Education | Review | Review |
| 09:30 AM | Finite Automata | Pushdown Automata | |
| 10:30 AM | Regular Expressions | CFG → PDA | Emptiness |
| 11:30 AM | NFAs | CF Pump | |
| Lunch | |||
| 01:30 PM | Closures | Turing Machines | |
| 02:30 PM | Regularity | TM Variants | |
| 03:30 PM | Pumping Lemma | Church-Turing Thesis | |
| 04:30 PM | Context Free Grammars | Acceptance | |
| Fri | Sat | Sun | |
|---|---|---|---|
| AM | *FAs | PDAs cont. | CNF |
| PM | Regular and CF Languages | Turing Machines |
Submit problem sets with by midnight AOE on the following Monday from being assigned via email link to cdeutschbein@lagrange.edu. Quarto rendered HTML on GitHub pages is preferred; Colab share or attached .ipynb is acceptable on the first three problem sets.
03 Feb - 07 Mar, 2025
| Week | Date | Talk | VoDS | PSet |
|---|---|---|---|---|
| 0x2 | 03 Feb | Diagonalization | Diagonalization | Finite Automata and Regular Languages |
| 0x3 | 10 Feb | Undecidability | Undecidability | Pushdown Automata and Context Free Grammars |
| 0x4 | 17 Feb | P and NP | P and NP | Turing Machines |
| 0x5 | 24 Feb | NP Completeness | ||
| 0x6 | 03 Mar | Cook-Levin Theorem |