CS 215 Homepage

Hw2 extended to Jan. 27, Thursday

Here is a preliminary version of the syllabus in PDF.

The following are the lecture notes (courtesy of M. Ogihara):

Introduction and preliminaries.

Regular languages and finite automata: part I and part II.

Context-free languages and grammars.

Pushdown automata.

Non-context-free languages and pumping lemma.

We will only be able to review the above topics briefly in class (they are supposed to be covered in CS150), while focusing on a few selected topics. You are thus required to review them (i.e. Chapters 0-2 of the textbook) carefully within the first three weeks of the quarter.

Turing machines and computability theory.

Decidability.

Undecidability and the Halting Problem.

Reducibility.

PCP and the mapping reducibility.

Time complexity classes.

The famous classes P and NP.

NP-completeness.

More examples of NP-complete problems.

Space complexity and Savitch's Theorem.

PSPACE and PSPACE-completeness.

Class NL.

Here are three chapters that we wrote for Algorithms and Theory of Computation Handbook: Formal Grammars and Languages, Computability, and Basic Notions in Computational Complexity. These chapters are not very technical and may help provide some high-level concepts about the theory.

Here is a copy of 2003's final.

The following mapping shows how your overall scores will be translated into letter grades at the end of the quarter: 90+ -> A+, 85+ -> A, 80+ -> A-, 77+ -> B+, 73+ -> B, 70+ -> B-, 67+ -> C+, 63+ -> C, 60+ -> C-, 57+ -> D+, 53+ -> D, 50+ -> D-, 49- -> F.