#
Readings for CS 3800

##
Required readings

- Read in textbook:
- Chapter 0 (Introduction)
- Section 1.1 (Finite Automata)
- Section 1.2 (Nondeterminism)
- Section 1.3 (Regular Expressions)
- Section 1.4 (Nonregular Languages)
- Section 2.1 (Context-Free Grammars)
- Section 2.2 (Pushdown Automata)
- Section 2.3 (Non-Context-Free Languages)
- Section 3.1 (Turing Machines)
- Section 3.2 (Variants of Turing Machines)
- Section 3.3 (The Definition of Algorithm)
- Section 4.1 (Decidable Languages)
- Section 4.2 (Undecidability)
- Section 5.1 (Undecidable Problems From Language Theory)
- Section 7.1 (Measuring Complexity)
- Section 7.2 (The Class P)
- Section 7.3 (The Class NP)
- Section 7.4 (NP-completeness)

- Read on the World-Wide Web:
- Read in textbook:
- Section 6.2 (Decidability of Logical Theories)

##
Optional Readings

- Slides on Quantum Computing
Slide 8 (tensor product) is incorrect.
The elements of the first column vector should be
x_{0} and x_{1}, the elements of the second should be
y_{0} and y_{1}, and the elements of the third should be
z_{0} and z_{1}.

Last updated 8 December 2015.

Click here to validate HTML on this page.