CourseCalendar

This calendar is generally reasonably correct for past dates, highly plausible for the current week or two, and a bit tentative beyond that point. It should firm up as the semester moves along and we settle into a rhythm....Also note that Sipser page numbers refer to the first edition. I'm trying to fix this but it is difficult without a copy of the second edition.

Sep 3 (F)	Lots of course setup/overview, some scheme.	For next time: Read Dybvig ch1 and 2 through exercise 2.2.1. Also review Sipser Part 0. Install DrScheme (or DrRacket or whatever it's now called).
Sep 7 (Tu)	More scheme basics (lambda define if). Recursive procedure definitions; higher order procedures.	For next time: The rest of Dybvig ch2. See also ResourcesForScheme.
Sep 10 (F)	More scheme: cons, recursion/iteration, stack, higher order procedures. Some orders of growth (big-Oh/Theta).	Look over ReadingRoom/AbstractDataTypes, ReadingRoom/OrdersOfGrowth, ReadingRoom/TailRecursion
Sep 14 (Tu)	Scheme data, interpreters (see ExpressionEvaluatorDotScm) and trees.	For next time: Assignment 1. Read Sipser 1.1 and 1.2 up and including the formal definition of a nondeterministic finite automaton (through ex. 1.18/p.54 in the first edition). Download JFLAP.
Sep 17 (F)	FSMs (D and ND); closure under regular operations; intro REs.	For next time: Sipser through 1.3 (equivalence of D and ND FSMs; intro regular expressions) except equivalence of regular expressions and finite automata (pp.66-76 in first edition) is optional. .
Sep 20 (Tu)	Equivalence of nondeterministic and deterministic FSMs; REs and FSMs	For next time: Sipser 1.4 (nonregular languages) and 2.2 (pushdown automata) only up to, not including equivalence with context-free grammars. In the first edition, the PDA section is Sipser pp. 101-106 (middle).
Sep 24 (F)	Pumping Lemma for Regular Languages. Pushdown Automata.	Also Assignment 2 due 9/28.
Sep 28 (Tu)	Quiz review, assorted topics.	Bring your questions. Review Cormen pp. 200-208 (stacks, queues, linked lists) or same topics in another algorithms book.
Oct 1 (F)	Class optional; may take exam during session	1st exam in pdf or Word formats, covering scheme, functional programming, array/list/stack/queue ADTs, basic algorithm analysis, FSMs, REs, PDAs
Oct 5 (Tu)	Trees as ADT. Log n. Searches/traversals. Heap implementation. Sorts (n^2 and n log n lower bound).	For next time: Review the following topics in Cormen or another algorithms book; understand at least one algorithm from each of the three categories: binary trees and binary search (Cormen pp. 253-264), n log n sorting algorithms -- heap, merge, and/or quick sorts (Cormen pp. 123-164), n-squared sorting algorithms -- insertion, selection, and/or bubble sort (Cormen pp. 15-37). Also please install gprolog.
Oct 8 (F)	Parsing/grammar; CFGs; Prolog parsing.	For next time: Sipser 2.1 and 2.2 (context free grammars and pushdown automata), BNF/Parsing material, Prolog grammar material (sections on context-free grammar, simple grammar rules, and any others you wish to read/skim)
Oct 12 (Tu)	More parsing; PDAs redux	Review/finish readings from last time.
Oct 15 (F)	PDA/CFG equivalence; limitations of CFGs.	For next time: Sipser 2.3 (non-context-free languages). Also Assignment 3 (sorts, trees, parsing, grammars, limitations) due 10/19
Oct 19 (Tu)	Propositional logic, boolean circuits, universality of NAND. NP nature of SAT	For next time: propositional logic handout; Sipser or Cormen on NP (Sipser section 7.3, but you may need to read 7.2 for it to make sense; Cormen Chapter 34.1 and 34.2).
Oct 22 (F)	Predicate logic and Prolog	For next time: predicate logic handout; prolog handout
Oct 26 (Tu)	More prolog. Backtracking.	For next time: Work on Assignment 4. You may also want to consult an additional prolog resource (from Union College)
Oct 29 (F)	Finishing up prolog; cut.	Assignment 4 (logic and prolog) due 11/2.
Nov 2 (Tu)	Quiz review, assorted topics.	Bring your questions.
Nov 5 (F)	Class optional; may take exam during session	2d exam
Nov 9 (Tu)	Beating the bounds. Hashtables, fast sorts (binsort, radix sort). Algorithmic strategies (divide and conquer, DP, greedy, etc.	Reading: relevant sections of Cormen (34; 8.3 and 8.4; also hashtables)
Nov 12 (F)	Olin Monday. No FOCS.
Nov 16 (Tu)	Turing machines. Complexity revisited.	For next time: Sipser 3.1 and 3.2
Nov 19 (F)	More Turing machines; building up to universal computation.	Reading: Sipser 4.1. Also review Sipser 7.1-7.4. Assignment 5 (Cheating, Turing machines, computability, universality) now due 12/7
T H A N K S G I V I N G -- B R E A K
Nov 30 (Tu)	Simulating machines. Universal computation. Limitations of computation. Halting. Metacircularity.	Reading: Sipser 4.2
Dec 3 (F)	Godel. Church/Turing.	Reading: Sipser 6.2 Assignment 5 due 12/7
Dec 7 (Tu)	Schedule Slack. We will slip or rearrange; I promise!
Dec 10 (F)	Exam review, assorted topics.	Bring your questions.
Dec 15-18	Final exam period	There will be a final exam in this class

Topics to draw from to fill in the schedule:

self balancing trees
relational databases, relational algebra
information retrieval (boolean, vector-space models)
machine learning
interpreters
compile-time vs. run-time; static analysis; typing
space-time tradeoff, dynamic programming
explicit discussion of algorithmic design strategies (divide and conquer, greedy, branch and bound, ...)
Graphs; TSP, Clique, more NP. Other graph algorithms. Read about graphs in your algorithms or discrete math book.

Leftovers from syllabus:

For next time: Read about graphs in your algorithms book.

	Graphs; BFS and DFS, spanning tree, shortest path, TSP approximation	Reading: relevant sections of Cormen (chapters 22, 23; 24.3 and previous parts of 24 that support it; 35.2) or other algorithms book
	Hashtables; relational algebra; semantic networks	Reading: Hashtables (from Cormen)
	More graph algorithms; Clique and NP; fast sorts (binsort, radix sort). Also algorithmic strategies (divide and conquer, DP, greedy, etc.)	Reading: relevant sections of Cormen (34; 8.3 and 8.4)