Instructor: Dr. Attila Sali

Text:  handouts ( László Lovász: Computational Complexity)
additional available readings: Cormen, Leiserson, Rivest: Algorithms, Aho, Hopcroft, Ullman:  The  Design  and Analysis of Computer  Algorithms, R. Sedgewick: Algorithms,  S. Baase: Computer Algorithms.

Prerequisite: some introductory combinatorics, algebra  and number theory (e.g. definitions  and  basic properties of graphs,  binomial coefficients,  primes  and groups) is  helpful.

Course description:
 

• Computing MIN, MAX, MINMAX,  sorting. The matrix multiplication algorithm of Strassen. Dynamic programming. The knapsack problem.
• Heapsort.
• Fibonacci heaps.  amoritzed cost.
• Turing Machines, universal Turing machines. RAM machines.
• The existence of universal Turing machines.
• Recursive functions. Recursive, recursively enumerable languages.
• Halting problem.  Kolmogorov-complexity of sequences.
• Storage and time,  general theorems on space and time complexity
• Non-deterministic Turing-machines.  NP and co-NP. Primes are in co-NP.
• Pratt's theorem: primes are in NP.
• Primes are in P.
• Cook's theorem: SAT is NP-complete.
• Other NP-complete problems. Non-approximability results.
• Communication games. Lower bounds to the communication complexity.