The official schedule for the semester is found on BYU Learning Suite. Here is the general template for the schedule for fall semester with the **Thanksgiving break**.

Week | Topic and Reading | Due |
---|---|---|

Week 1 | Course overview, sets, strings, languages, and expressiveness (2.1, 2.2, 2.3, and 13.2) | |

Sets, functions, and finite state machines with outputs | Homework 0 | |

Week 2 | Finite state machines, multiple outputs, no output, and regular expressions (13.2 and 13.3) | Homework 1 |

Regular expressions and the Lexical Analyzer See scanner-algorithm.pptx (13.1 and 13.4) | ||

Week 3 | Grammars, derivations, and parse trees (13.1) | Homework 2 |

Top-down parsing (recursive descent, removing left-recursion, LL(1)) See top-down-parsing.pptx | ||

Week 4 | Top-down parsing and the Datalog Parser | Homework 3 |

Propositional logic, logical equivalences, tautologies, and contradictions (1.1, 1.2, and 1.3) | Lexical Analyzer | |

Week 5 | Predicates, quantifiers, and predicate logic equivalences (1.4) | Homework 4 |

Validity, equivalences, locgical implications, and derivations (1.6) | Datalog Parser Part 1 | |

Week 6 | Inference and resolution with predicate calculus and derivations (1.6 and 1.7) | Homework 5 |

Solving Datalog queries with resolution and proof by contradiction | Datalog Parser Part 2 | |

Week 7 | Resolution and inference | |

Relational Algebra (9.1, 9.2, and 9.3) See relational-algebra.pptx | Midterm 1 | |

Week 8 | Closures, equivalence relations, and relational algebra (9.4, 9.5, 9.6) | Homework 6 |

Relational algebra, relational databases, and Datalog Interpreter (9.5 and 9.6) | Relational Database Part 1 | |

Week 9 | Equivalence relations and partial orders | Homework 7 |

Graphs, adjacency lists, matrices, Warshall's algorithm, Floyd's algorithms (10.1 and 10.3) | Relational Database Part 2 | |

Week 10 | Depth-first search, breadth first search, strongly connected components (10.4) | Homework 8 |

Strongly connected components, and Optimizing Rule Evaluation | ||

Week 11 | Dijkstra's Algorithm (10.6) | |

Trees and tree traversal (11.1, 11.2, and 11.3) | Midterm 2 and Datalog Interpreter Part 1 | |

Week 12 | Spanning trees and minimal spanning trees (11. 4 and 11.5) | Homework 9 |

Minimal spanning trees (11.5) | Datalog Interpreter Part 2 | |

Week 13 | Thanksgiving Break | |

Week 14 | Induction (5.1, 5.2, 5.3) | Homework 10 |

Induction (5.4 and 5.5) | Optimizing Rule Evaluation Part 1 | |

Week 15 | Induction | Homework 11 |

Course Wrap-up and Review | Optimizing Rule Evaluation Part 2 | |

Week 16 | Finals | Final |

- Course overview and Sets, strings, languages and expressiveness
- Sets, functions, and finite state machines with outputs. Sections 2.1, 2.2, 2.3, and 13.2 of text
- Finite state machines with multiple outputs, finite state machines with no output, and regular expressions. Sections 13.2 and 13.3. Wikipedia finite state machine, finite state transducer, and regular expressions.
- Regular expressions, lexical analysis (scanning), and project 1. Section 13.1 and 13.4.
- Grammars, derivations, and parse trees. Section 13.1.
- Top-down parsing (Recursive descent, removing left-recursion, LL(1) parsing).
- Top-down parsing and project 2. (Left-factoring, FIRST sets, FOLLOW sets, building LL(1) parse tables).
- Propositional logic, logical equivalences, tautologies, and contradictions. Section 1.1, 1.2, and 1.3.
- Predicates, quantifiers, and predicate logic equivalences. Section 1.4.
- Midterm I review
- Validity, equivalences, logical implications, derivations. Section 1.6.
- Resolution with propositional calculus, derivations, proof by deduction, and proof by contradiction. Sections 1.6 and 1.7.
- Resolution with predicate calculus and resolution in Datalog. Proof by contradiction.
- Induction. Sections 5.1 and 5.2 (add in rest of Chapter 5 that treats structural recursion, induction, and program proofs).
- Induction and Strong induction
- Induction, Strong Induction, and Well-ordering (shallow)
- Relational Algebra. Sections 9.1, 9.2, and 9.3
- Relational algebra. Section 9.4 and 9.5.
- Relational algebra. Sections 9.4 and 9.5.
- Equivalence relations and partial orders. Sections 9.5 and 9.6.
- Midterm II review
- Partial orders, , Hasse Diagrams, and Topological sort.
- Graph definitions, applications, adjacency lists, adjacency matrices, and connectivity. Warshall's Algorithm. Sections 3.2, 10.1, 10.2, 10.3, and 10.4 (ignores most of the different applications)
- Dijkstra's Algorithm. Floyd's Algorithm. Section 10.6.
- Depth-first search, breadth-first search, traversal orders (in-pre-post), spanning trees, and strongly connected components. Framed in context of Datalog rule evaluation optimization. Sections 11.1, 11.2, 11.3, and 11.4.
- Computing strongly connected components. Prim's and Kruskal's minimum spanning tree computation. Section 11.5.
- Final review

For reference, here is the Winter 2013 schedule used by Dr. Embley and Dr. Goodrich.