**Lecture notes (in Russian):**

Part I:

- Lecture 1:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Matrix multiplication and its verification. Matrix inversion. Communication complexity of string comparison. Pattern matching. - Lecture 2:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Schönhage-Strassen integer multiplication algorithm. - Lecture 3:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Online algorithms. - Lecture 4:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Approximation algorithms for MAX CUT and the cardinality of the union of sets. - Lecture 5:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Randomized algorithm for All-Pairs Shortest Paths.

Part II:

- Lecture 6:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

MIN CUT, minimum spanning tree, deterministic pattern matching. - Lecture 7:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Linear programming. - Lecture 8:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Primality. Planar graph drawing. Parallel algorithm for MIS. - Lecture 9:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Approximation algorithms for Knapsack, Set Cover, Graph Colouring, and Metric TSP. - Lecture 10:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Randomized algorithm for 3-SAT. Approximation algorithm for MIN VC. Maximum flow. - Lecture 11:
TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Deterministic approximation algorithm for DNF Counting.

**Program**
of the first exam (corresponds to Lectures 1-5):

TeX source,
Postscript file,
compressed Postscript file,
PDF file.

**Program**
of the second exam (corresponds to Lectures 6-11):

TeX source,
Postscript file,
compressed Postscript file,
PDF file.

Back to Home Page