[FrontPage] [TitleIndex] [WordIndex

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:

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)

2013-07-17 10:42