search
This schedule is subject to change.
| Date | Topic | Reading | Due |
|---|---|---|---|
| May 1 | Course overview, sets, strings, and languages | Syllabus, 2.1, 2.2, 2.3 | |
| May 3 | Languages and expressiveness; finite state machines | 13.2, 13.3 | Homework 0 |
| May 6 | Regular expressions and FSMs, Lexical Analyzer | 13.4, Lexical Analyzer, scanner-algorithm.pptx | Homework 1 |
| May 8 | Grammars, derivations, and parse trees | 13.1, top-down-parsing.pptx | Homework 2 |
| May 10 | Top-down parsing, Datalog Parser | top-down-parsing.pptx, Datalog Parser | |
| May 13 | Propositional logic, logical equivalences, tautologies, and contradictions | 1.1, 1.2, 1.3 | Homework 3 |
| May 14 | Lexical Analyzer | ||
| May 15 | Predicates, quantifiers, and their logical equivalences | 1.4 | Homework 4 |
| May 17 | Validity, equivalences, logical implications, and derivations; Inference and resolution | 1.6 | |
| May 20 | Inference and resolution, continued; Datalog queries with resolution | 1.7 | Homework 5, Midterm 1 |
| May 21 | Datalog Parser Part 1 | ||
| May 22 | Relations, Relational Database | 9.1, 9.2, Relational Database | |
| May 24 | Relational algebra, closures, equivalence relations | 9.3, 9.4, 9.5, relational-algebra.pptx | Homework 6 |
| May 27 | Memorial Day holiday | ||
| May 28 | Datalog Parser Part 2, Homework 7 | ||
| May 29 | Datalog Interpreter, Equivalence relations and partial orders | 9.6, Datalog Interpreter | |
| May 30 | Relational Database Part 1 | ||
| May 31 | Graphs, adjacency lists, matrices | 10.1, 10.3 | Homework 8 |
| June 3 | Warshall's algorithm, Floyd's algorithm; Depth-first search, breadth first search | 10.4 | Midterm 2 |
| June 4 | Relational Database Part 2 | ||
| June 5 | Strongly connected components, Optimizing Rule Evaluation | Optimizing Rule Evaluation | |
| June 7 | Dijkstra's Algorithm; Trees | 10.6, 11.1, 11.2 | Datalog Interpreter Part 1 |
| June 10 | Tree traversal, spanning trees | 11.3, 11.4 | Homework 9 |
| June 12 | Minimal spanning trees; Induction | 11.5, 5.1, 5.2, 5.3 | |
| June 14 | Induction, continued | 5.4, 5.5 | Datalog Interpreter Part 2, Optimizing Rule Evaluation Part 1, Homework 10 |
| June 15 | Homework 11 | ||
| June 17 | Course wrap-up | Optimizing Rule Evaluation Part 2 |
