Topics
| Topic | Readings |
|---|---|
| Accepting languages | |
| Alternative DFA representations | hopcroft2 §2.2.2-2.2.5 |
| Applications of regular expressions | hopcroft2 §3.3 |
| Backus-Naur form | |
| Basics of Haskell | Haskell doc ("Prelude"), Learn you a Haskell |
| Basics of Perl | |
| C# and polymorphism | |
| CFG derivations | hopcroft2 §5.1.4-5.2.2 |
| Case-based code generation | |
| Church-Turing thesis | |
| Code generation cont'd | |
| Complexity and P | hopcroft2 §10.0-10.1.2 |
| Context-free grammars | hopcroft2 §5.1-5.1.3 |
| Contradiction proofs | hopcroft2 §1.3.2-1.3.4 |
| Decidability | hopcroft2 §8.1 |
| Finite automata | hopcroft2 §2.1-2.2.1 |
| Functions and relations | |
| Grammars | |
| Grammars for Scheme, C, Perl | |
| Integer induction | hopcroft2 §1.4.1 |
| Interpreting vs compiling | |
| Intro to C# | |
| Intro to LaTeX | Overleaf LaTeX tutorial |
| Intro to Racket | Racket website, Racket documentation |
| Lambda calculus | |
| Languages as sets of strings | hopcroft2 §1.5 |
| Languages as syntax | |
| Lazy evaluation and currying in Haskell | |
| Logic review | |
| More Racket | Racket modules (require, provide), Testing in Racket |
| More recursive functions | |
| Nondeterministic finite-state automata | hopcroft2 §2.3.1-2.3.2 |
| Parse trees | |
| Parsers | hopcroft2 §5.3-5.3.1 |
| Parsing to abstract syntax trees | |
| Perl-compatible regular expressions | |
| Proofs | hopcroft2 §1.2 |
| Racket first-class functions | |
| Racket lists and recursive functions | |
| Recurrence relations in analysis | |
| Recursive definitions | |
| Recursively enumerable languages | |
| Regular expressions | hopcroft2 §3.1 |
| Regular expressions and FSAs | hopcroft2 §2.5.1-2.5.2 |
| Review Big-O notation | |
| Review language translation pipeline | |
| Sets review; set equivalence | hopcroft2 §1.3.1 |
| Static and dynamic type checking | |
| Structural induction | hopcroft2 §1.4.3-1.4.4 |
| Syntax-driven semantics | |
| The Master theorem | Master theorem |
| The halting problem | hopcroft2 §9.1-9.2 |
| The pumping lemma | hopcroft2 §4.1 |
| Tokenising LISP-family languages | |
| Turing machines | hopcroft2 §8.2-8.2.3
Manufactoria (game) |
| Type inference in Haskell | Haskell doc ("Prelude") |
| Verifiability, NP, and NP-completeness | hopcroft2 §10.1.3-10.2.1 |