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