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

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.

cs-236/schedule.txt · Last modified: 2016/08/29 23:06 by egm
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0