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