Course Calendar

Thurs, Jan 14

• Course organization and overview
  • Introductions
  • Office hours
  • Bibliography
  • Grading policy
  • Programming assignments and related lab issues
  • Course overview: Motivation for formal systems
• Assignments
  • Get lab account (see Marty in Rm. 735 CSB)
  • Review background material on WWW and Unix
  • Review material on data structures, algorithm analysis, and C++
  • Read chapter 8.1, 8.2 in text

Tues, Jan 19

• Relations
  • Motivation
  • Definitions
  • Implementation structures
• Assignments
  • Read chapter 8.3, 8.4, 8.5
  • Programming assignment: Relational database

Thurs, Jan 21

• Relations
  • Indexes
  • Operations that span relations
  • Database design
• Assignments
  • Read chapter 8.6

Tues, Jan 26

• Relations
  • Relational algebra
• Assignments
  • Programming assignment 1, databases, Part I, due
  • Read chapter 8.7, 8.8, 8.9

Thurs, Jan 28

• Relations
  • Implementations of join
  • Query optimization
• Assignments
  • Read chapter 9.1, 9.2, 9.3

Tues, Feb 2

• Graphs
  • Definitions
  • Implementations
• Assignments
  • Programming assignment 1 databases, Part II, due
  • Programming assignment: Graphs and the Jug Problem

Thurs, Feb 4

• Graphs
  • Breadth- and depth-first search

Tues, Feb 9

• Graphs
  • Reachability
  • Postorder numbering
  • Testing for cycles
  • single-source shortest-path problem

Thurs, Feb 11

• Graphs
  • all-pairs-shortest-path problem
  • transitive closure

Tues, Feb 16

• Graphs
  • minimum cost spanning tree
• Assignments
  • Programming assignment 2, graphs and jug problem, due

Thurs, Feb 18

• Finite Automata
  • deterministic FA
  • programs from FA
  • nondeterministic FA
• Assignments
  • Programming assignment: C++ Scanner

Tues, Feb 23

• Finite Automata and Regular Expressions
  • subset construction
  • regular expressions
• Assignments
  • Written Assignment: Chapter 10 problems on finite automata

Thurs, Feb 25

• Finite Automata and Regular Expressions
  • equivalence of regular expressions and FA
  • Lex

Tues, Mar 2

• Midterm exam
• Assignments
  • Exercises from chapter 10 due.

Thurs, Mar 4

• Context free grammars
• Assignments
  • C++ Scanner project due

Tues, Mar 16

• Parse trees
• Assignments
  • Programming assignment: Scientific Calculator

Thurs, Mar 18

• Top-down parsing

Tues, Mar 23

• First, Follow, and Predict sets

Thurs, Mar 25

• Table-driven parsing

Tues, Mar 30

• Propositional Logic

Thurs, April 1

• Propositional Logic cont.

Tues, April 6

• Propositional Logic cont.
• Assignments
  • Calculator Project Due
  • Written Assignment: Proof by resolution

Thurs, April 8

• No Class due to National Undergraduate Research Conference. (But you get to start looking at a programming assignment anyway.)
• Assignments
  • Programming assignment: Prolog

Tues, April 13

• Predicate Logic
• Assignments
  • Resolution assignment due

Thurs, April 15

• Predicate Logic cont.

Tues, April 20

• Computability

Thurs, April 22

• Computability cont.
• Assignments
  • Prolog Assignment Due

Tues, April 27

• Computability cont.

Thurs, May 6

• Final Exam. 4:00 PM, CSB 601.