Instructor: Dr Gyula Y. KATONA

Text:  Michael Sipser:  Introduction to the Theory of Computation, Springer

Prerequisite: Prerequisite: some introductory combinatorics (e.g. definitions and basic properties of graphs, binomial coefficients, primes) is helpful, but not absolutely necessary.

Course description:

The course has very little connection to programming, you don't need to know how to write programs. It is about the theoretical questions that arise from computers. Consider it more mathematics than computer science. However, nowadays every mathematician should know something about complexity theory.

Homework: 4 problems/week (1 easy, 2 medium, 1 hard). Working in groups is allowed, but write down your own version of the solution (and be sure it is correct). The worst 2 homework sets are dropped.
Midterm: 6 problems, open book, open notes, 2 hours in class
Final: 2 theory questions, closed book; 4 problems, open book, open notes, 2 hours in class
Homework 30%, Midterm 30%, Final 40%
90% A+, 85% A, 80% A-, 75% B+, 70% B