Overview
The course covers basic concepts, methods and results from Theoretical Computer Science at the advanced undergraduate / beginning graduate level. The two main areas covered are Models and Complexity of Computing and Algorithms.
Schedule: Tu Thr 2.30pm3:45pm
Syllabus: ps pdf
TA
Pradipta Mitra
Office Hours: Wed 3:004:30 or by appointment
Handouts

Finite Automata and Regular Expressions I ps pdf

Finite Automata and Regular Expressions II ps pdf

Dynamic Programming ps pdf

Turing Machines ps pdf

Time and Space Complexity I ps pdf

Time and Space Complexity II ps pdf

Recursive and R.E. Sets ps pdf

Oracles ps pdf

NP Completeness ps pdf

Enumerating Sets ps pdf

Context Free Grammars I ps pdf

Context Free Grammars II ps pdf

Maximum Matchings in Graphs ps pdf

Algorithms for integers, polynomials ps pdf

Linear Programming ps pdf

Subset Sum Problem ps pdf
Assignments

Assignment 1 ps pdf
Due date: Feb 1, 2005

