# Topics

Topics | hopcroft2 |
hopcroft3 |
Web links | ||
---|---|---|---|---|---|

11 Jan | R/1 | Languages as syntax, Grammars, Intro to LaTeX | Overleaf LaTeX tutorial | ||

16 Jan | T/2 | Logic review, Proofs | 1.2 | ||

18 Jan | R/2 | Sets review; set equivalence, Functions and relations | 1.3.1 | ||

23 Jan | T/3 | Contradiction proofs, Intro to Racket | 1.3.2-1.3.4 | Racket website; Racket documentation | |

25 Jan | R/3 | More Racket | Racket modules (require, provide); Testing in Racket | ||

30 Jan | T/4 | Recursive definitions, Integer induction, Racket lists and recursive functions | 1.4.1 | ||

01 Feb | R/4 | Structural induction, More recursive functions | 1.4.3-1.4.4 | ||

06 Feb | T/5 | Languages as sets of strings, Racket first-class functions | 1.5 | ||

08 Feb | R/5 | Finite automata | 2.1-2.2.1 | ||

13 Feb | T/6 | Accepting languages, Alternative DFA representations, Basics of Perl | 2.2.2-2.2.5 | ||

15 Feb | R/6 | Nondeterministic finite-state automata, Regular expressions and FSAs | 2.3.1-2.3.2, 2.5.1-2.5.2 | ||

20 Feb | T/7 | Regular expressions, Perl-compatible regular expressions | 3.1 | ||

22 Feb | R/7 | Applications of regular expressions, Tokenising LISP-family languages | 3.3 | ||

27 Feb | T/8 | The pumping lemma | 4.1 | ||

29 Feb | R/8 | ||||

12 Mar | T/10 | Context-free grammars, Backus-Naur form, Grammars for Scheme, C, Perl | 5.1-5.1.3 | ||

14 Mar | R/10 | CFG derivations, Parse trees, Intro to C# | 5.1.4-5.2.2 | ||

19 Mar | T/11 | Parsers, Parsing to abstract syntax trees, Syntax-driven semantics | 5.3-5.3.1 | ||

26 Mar | T/12 | Review language translation pipeline, Interpreting vs compiling, Case-based code generation, C# and polymorphism | |||

28 Mar | R/12 | Code generation cont'd | |||

02 Apr | T/13 | Decidability | 8.1 | ||

04 Apr | R/13 | Basics of Haskell, Turing machines | 8.2-8.2.3 | Haskell doc ("Prelude"); Learn you a Haskell; Manufactoria (game) | |

11 Apr | R/14 | Type inference in Haskell, Static and dynamic type checking, Lazy evaluation and currying in Haskell | Haskell doc ("Prelude") | ||

16 Apr | T/15 | Lambda calculus, Church-Turing thesis | |||

18 Apr | R/15 | Recursively enumerable languages, The halting problem, Review Big-O notation, Complexity and P | 9.1-9.2, 10.0-10.1.2 | ||

23 Apr | T/16 | Recurrence relations in analysis, The Master theorem | Master theorem | ||

25 Apr | R/16 | Verifiability, NP, and NP-completeness | 10.1.3-10.2.1 |