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.