CS500, Introduction to the Theory of Computation

Basics:
	Defining inputs, algorithms, and complexity
	Asymptotics and Moore's law

Automata and languages
	DFAs and NFAs
	Closure properties
	Equivalence classes and minimal automata
	The Pigeonhole Principle and the Pumping Lemma
	Context-free grammars

Algorithm review
	Recursion: Towers of Hanoi
	Greedy algorithms: Minimum Spanning Trees
	Divide-and-conquer: Sorting
	Dynamic programming: Genome Alignment 
	Max Flow and Min Cut
	Perfect Matching and reductions

NP-completeness
	Boolean circuits and formulas
	3-SAT and NAESAT
	Graph coloring
	Independent Sets, Vertex Covers, and Cliques
	Integer Linear Programming
	What if P=NP?  Proofs and creativity

The Grand Unified Theory of Computation
	Universal computation and interpreting programs
	1936: Turing machines, lambda-calculus, and partial recursive functions
	Diagonalization
	The Halting Problem, self-reference, and undecidability

Randomness and Approximation
	The Birthday Problem and hash functions
	Coupon Collecting
	Fingerprinting and the primes
	Karger's Min Cut algorithm
	Walk-SAT
	Relaxation and rounding: the 2-approximation for Vertex Cover
	Christofides' 3/2-approximation for TSP

Memory [optional]
	Log-space and Reachability
	Games, Quantifiers, and PSPACE

More topics [optional]
	Secret Sharing
	RSA cryptography
	Diffie-Helman key exchange
	Quantum computing: Shor's factoring algorithm