This schedule is subject to change.
Date | Topic | Reading | Due |
---|---|---|---|
Sep 5 | Course overview, sets | ||
Sep 7 | sets, strings, and languages | 2.1, 2.2, 2.3 | |
Sep 10 | Languages and expressiveness; finite state machines with single outputs | 13.2 | Homework 0 |
Sep 12 | Finite state machines, multiple outputs, no output, and regular expressions | 13.3 | |
Sep 14 | Regular expressions and FSMs | 13.1, 13.4 | Homework 1 |
Sep 17 | Lexical Analyzer See scanner-algorithm.pptx | Lexical Analyzer | |
Sep 19 | Grammars, derivations | Homework 2 | |
Sep 21 | Parse trees | top-down-parsing.pptx | |
Sep 24 | Top-down parsing (recursive descent, removing left-recursion, LL(1)) See top-down-parsing.pptx | ||
Sep 26 | Datalog Parser | Datalog Parser | |
Sep 28 | Propositional logic | 1.1, 1.2 | Homework 3 |
Oct 1 | Logical equivalences, tautologies, and contradictions | 1.3 | |
Oct 2 | Lexical Analyzer | ||
Oct 3 | Predicates and quantifiers | 1.4 | Homework 4 |
Oct 5 | Predicate logic equivalences | ||
Oct 8 | Validity, equivalences, logical implications, and derivations | 1.6 | |
Oct 9 | Datalog Parser Part 1 | ||
Oct 10 | Inference and resolution with predicate calculus and derivations | 1.7 | Homework 5 |
Oct 12 | Inference and resolution with predicate calculus and derivations | Midterm 1 | |
Oct 15 | Solving Datalog queries with resolution and proof by contradiction | ||
Oct 16 | Datalog Parser Part 2 | ||
Oct 17 | Relations | 9.1, 9.2 | |
Oct 19 | Relational Database | Relational Database | |
Oct 22 | Relational algebra | 9.3, relational-algebra.pptx | |
Oct 24 | Closures, equivalence relations | 9.4, 9.5 | Homework 6 |
Oct 26 | Relational databases | ||
Oct 29 | Datalog Interpreter | Datalog Interpreter | |
Oct 30 | Relational Database Part 1 | ||
Oct 31 | Equivalence relations and partial orders | 9.6 | Homework 7 |
Nov 2 | Graphs, adjacency lists, matrices | 10.1, 10.3 | |
Nov 5 | Warshall's algorithm, Floyd's algorithm | ||
Nov 6 | Relational Database Part 2 | ||
Nov 7 | Depth-first search, breadth first search | 10.4 | Homework 8 |
Nov 9 | Strongly connected components | ||
Nov 12 | Optimizing Rule Evaluation | Optimizing Rule Evaluation | |
Nov 14 | Dijkstra's Algorithm | 10.6 | |
Nov 16 | Trees | 11.1, 11.2 | |
Nov 19 | Tree traversal | 11.3 | Homework 9 |
Nov 20 | Spanning trees | 11. 4 | |
Nov 26 | Minimal spanning trees | 11.5 | Datalog Interpreter Part 1 |
Nov 28 | Induction | 5.1, 5.2, 5.3 | Midterm 2 (scheduled M-F) |
Nov 30 | Induction | 5.4, 5.5 | Homework 10 and Datalog Interpreter Part 2 |
Dec 3 | Induction | ||
Dec 4 | Optimizing Rule Evaluation Part 1 | ||
Dec 5 | Induction | Homework 11 | |
Dec 7 | Course Wrap-up | ||
Dec 10 | Final review | ||
Dec 11 | Optimizing Rule Evaluation Part 2 | ||
Dec 12 | Final review |
The tentative schedule of topics for the last two weeks for section 1 (Peter Aldous) is:
Date | Topic |
---|---|
Dec 3 | C++ memory |
Dec 5 | Graph theory: Eulerian and Hamiltonian walks |
Dec 7 | TBD |
Dec 10 | Review midterms 1 and 2 |
Dec 12 | Final review |