Efficient Algorithms (2001)

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.