Syllabus calendar
Click on a day to see full information for that day, including topic
list, suggested readings, questions, and other information. This page
will be updated throughout the term.
| 1 |
[no class]
|
11 Jan
Languages as syntax,
Grammars,
Intro to LaTeX
|
| 2 |
16 Jan
Logic review,
Proofs
Hwk 0 due
|
18 Jan
Sets review; set equivalence,
Functions and relations
Hwk 1 out
|
| 3 |
23 Jan
Contradiction proofs,
Intro to Racket
Hwk 1 due
|
25 Jan
More Racket
Hwk 2 out
|
| 4 |
30 Jan
Recursive definitions,
Integer induction,
Racket lists and recursive functions
Hwk 2 due
Hwk 1 revision due
|
1 Feb
Structural induction,
More recursive functions
Hwk 3 out
|
| 5 |
6 Feb
Languages as sets of strings,
Racket first-class functions
Hwk 3 due
Hwk 2 revision due
Hwk 4 out
|
8 Feb
Finite automata
|
| 6 |
13 Feb
Accepting languages,
Alternative DFA representations,
Basics of Perl
Hwk 4 due
|
15 Feb
Nondeterministic finite-state automata,
Regular expressions and FSAs
Hwk 5 out
|
| 7 |
20 Feb
Regular expressions,
Perl-compatible regular expressions
Hwk 5 due
Hwk 4 revision due
|
22 Feb
Applications of regular expressions,
Tokenising LISP-family languages
Hwk 6 out
|
| 8 |
27 Feb
The pumping lemma
Hwk 6 due
Hwk 5 revisions due
|
29 Feb
Exam 1
|
| 9 |
[no class]
|
[no class]
|
| 10 |
12 Mar
Context-free grammars,
Backus-Naur form,
Grammars for Scheme, C, Perl
|
14 Mar
CFG derivations,
Parse trees,
Intro to C#
Hwk 7 out
|
| 11 |
19 Mar
Parsers,
Parsing to abstract syntax trees,
Syntax-driven semantics
Hwk 7 due
Hwk 8 out
|
[no class]
|
| 12 |
26 Mar
Review language translation pipeline,
Interpreting vs compiling,
Case-based code generation,
C# and polymorphism
Hwk 8 due
|
28 Mar
Code generation cont'd
Hwk 9 Out
|
| 13 |
2 Apr
Decidability
Hwk 9 due
Hwk 7 revisions due
|
4 Apr
Basics of Haskell,
Turing machines
Hwk 10 out
|
| 14 |
[no class]
|
11 Apr
Type inference in Haskell,
Static and dynamic type checking,
Lazy evaluation and currying in Haskell
Hwk 10 due
Hwk 9 revision due
Hwk 11 out
|
| 15 |
16 Apr
Lambda calculus,
Church-Turing thesis
Hwk 11 due
|
18 Apr
Recursively enumerable languages,
The halting problem,
Review Big-O notation,
Complexity and P
|
| 16 |
23 Apr
Recurrence relations in analysis,
The Master theorem
Hwk 10 revision due
Hwk 11 revision due
|
25 Apr
Verifiability, NP, and NP-completeness
Exam 2
1 May
|