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 |