search
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 |
