Algorithms and Complexity

Introduction of selected topics.

Interactive proofs -- a possible generalization of NP. Strong and weak players,  the AM and IP classes. Probabilistically checkable proofs.

 Communication complexity : computation with minimal information exchange. Connection to the matrix of the function. Nondeterministic complexity and its relation to deterministic complexity. Randomized protcols and their efficiency.

 Geometrical algorithms: computations without division, closest pair of points, efficient convex hull computation .

Advanced search techniques: k-th element in linear time, computation of rank. How to store intervals

Pattern matching: KMP and Boyer-Moore algorithms. Pattern matching by finite automaton. Matching with errors, approximate solutions, and the efficient computation of edit distanc.

 Parallel algorithms: variants of the PRAM model. Comparisons for simple cases.  Computations organized in binary trees. The effect of changing the numer of processors (Brent's theorem)

 Parallel algorithms for sorting (Batcher). Prefix sum computation and its applications. Computation of ranks.

Distributed algorithms: theoretical model. Leader selection algorithms on rings and on general graphs.

Distributed algorithms whith failers: fails in lines, when processors stop, and byzantine errors.

 Network topologies from graph theoretical point of view: grid, cube, cube connected cycel, butterfly, Benes(shortest paths, diameter, cuts). Embeddings,algorithmical aspects.

 Random graphs: different models, their basic properties (degrees, paths, connectedness). Random graphs as models of networks.

Parametric complexity: NP-hard problems with efficient solution for small values of a parameter.  Bounding the depth of a search tree.Grpah minor theorem and consequences. The kernel method. W[1] complexity.

On-line algorithms: measure of effifiency. Examples. Scheduling algorithms.

Quantum computation:  tools from linear algebra, simple algorithms (teleporting, Deusch-Jozsa). Qunatum Fourier transformation, the idea of prime factorization. Quantum cryptography.