search
Table of Contents
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 (section 3.4 of this chapter), 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 |
Spring 2019 Schedule
The schedule for Spring 2019, taught by Professor Aldous, can be found at Spring 2019 Schedule.
Fall 2018 Schedule
The schedule for Fall 2018, taught by Professors Woodfield and Aldous, can be found at Fall 2018 Schedule.
Winter 2014 Schedule
- 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
Winter 2013 Schedule
For reference, here is the Winter 2013 schedule used by Dr. Embley and Dr. Goodrich.
