Fundamentals of Computer Science (Spring 14)

Preliminary lecture plan and reading instructions

We stress that the plan below is preliminary and subject to change during the course.

All chapter numbers below refer to

Peter Linz, An Introduction to Formal Languages and Automata, Fifth edition, International edition, Jones & Bartlett Learning, 2012.

  • Lecture 1 (Jan. 20) Introduction. Lanugages and finite automata. Ch. 1, 2.1
  • Lecture 2 (Jan. 22) DFA minimization. Nondeterministic finite autmata. Ch. 2.2, 2.4
  • Lecture 3 (Jan. 23) Equivalence of NFA and DFA. Regular expressions.Ch. 2.3, 3.1, 3.2
  • Assignment 1 Due February 3.
  • Lecture 4 (Feb. 3) Properties of the regular languages. Ch. 4
  • Lecture 5 (Feb. 6) Context-free grammars and languages. Ch. 5
  • Assignment 2 Due February 12.
  • Lecture 6 (Feb. 10) CFG normal forms. The CYK algorithm. Pushdown automata. Ch. 6, 7.1
  • Lecture 7 (Feb. 13) PDA and context-free languages. Properties of the context-free languages. Ch. 7.2, 7.3, 8
  • Assignment 3 Due February 17
  • Lecture 8 (Feb. 17) Turing machines. Ch. 9.1, 9.2
  • Lecture 9 (Feb. 20) The Church-Turing thesis. Nondeterministic TMs. Universal TMs. Ch. 9.3, 10.3, 10.4
  • Lecture 10 (Feb. 24) Recursive and recursively enumerable languages. The Chomsky Hierarchy. Ch. 11
  • Assignment 4 Due February 27.
  • Lecture 11 (Feb. 27) Undecidability. The halting problem. Ch. 12.1, 12.2
  • Assignment 5 Due March 3.
  • Lecture 12 (Mar. 3) Reductions. More undecidability. Ch. 12.3, 12.4
  • Lecture 13 (Mar. 6) The classes P and NP. Polynomial time reductions. NP-completeness. Ch. 14
  • Assignment 6 Due March 17.
  • Lecture 14 (Mar. 17) The SAT problem. Cook's theorem. More NP-complete problems. Current research.
  • WRITTEN EXAM March 24.