The official schedule for the semester is found on [http://learningsuite.byu.edu 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 [[Lectures | 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 [[Lectures | 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 | 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 | Datalog Parser Part 2]] | | Week 7 | Resolution and inference | | | | Relational Algebra (9.1, 9.2, and 9.3) See [[Lectures | relational-algebra.pptx]] | [[Exams | 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 | 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 | 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 ''[https://people.eecs.berkeley.edu/~vazirani/algorithms/chap3.pdf chapter]''), and [[Optimizing Rule Evaluation]] | | | Week 11 | Dijkstra's Algorithm (10.6) | | | | Trees and tree traversal (11.1, 11.2, and 11.3) | [[Exams | Midterm 2]] and [[Datalog Interpreter | 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 | 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 | Optimizing Rule Evaluation Part 1]]| | Week 15 | Induction | [[Homework 11]] | | | Course Wrap-up and Review | [[Optimizing Rule Evaluation | Optimizing Rule Evaluation Part 2]] | | Week 16 | Finals | [[Exams | 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 [http://students.cs.byu.edu/~cs236ta/winter2013MWF/index.html Winter 2013 schedule] used by Dr. Embley and Dr. Goodrich.