Instructor: Dr. Gábor TARDOS

Text: Cormen, Leiserson, Rivest: Algorithms;
additional available readings: 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:

Communication games. Lower bounds to the communication complexity.
Randomized protocol for the Encyclopedia Britannica problem (ID function) (Rabin and Simon). Thompson's theorem for VLSI design.
Computing MIN, MAX, MINMAX,  sorting.
The algorithm of Karatsuba and Ofman. The matrix multiplication algorithm of Strassen. Dynamic programming. The knapsack problem.
The scaling method of Ibarra and Kim.
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.
Non-deterministic Turing-machines.  NP and co-NP. Primes are in co-NP.
Pratt's theorem: primes are in NP.
Cook's theorem: SAT is NP-complete.
Other NP-complete problems. Non-approximability results.