What is an algorithm 2

Algorithms II

• Introduction: The satisfiability problem, 2-Sat, probabilistic algorithm for 2-SAT.

• NP completeness: meaning, examples.

• Graph algorithms: minimal cut, shortest paths between all pairs of nodes, matching, the marriage problem, 3-colorability.

• Algebraic and number theoretic algorithms: multiplication of large numbers, matrix multiplication, modular exponentiation, factorization: Pollard's rho and (p-1) algorithms, quadratic sieve.

• Approximation algorithms: 0/1 Rucksack, Max-Cut, Traveling-Salesman and Delta-TSP, Max-k-SAT, # DNF-SAT

• Parameterized algorithms. Basic methods: restricted search trees, reduction to the core of the problem, graph properties that can be changed, color coding.

• On-line algorithms: The paging problem and the distribution of work problem: deterministic and probabilistic algorithms.

leafLecture materialMaterial / linkscorrection
page 1Cover, SAT, complexity classes
page 2

Turing reduction, min cut

Sheet 3APD algorithmJava Matrix Package
Sheet 4APSP algorithmProposed solution
Sheet 5Matching
Sheet 6Matching
  • T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press, 1990.
  • M.R. Garey, D.S. Johnson: Computers and Intractability - A Guide to the Theory of NP Completeness. Freeman, 1979.
  • A. Gibbons, W. Rytter: Efficient Parallel Algorithms. Cambridge University Press, 1988.
  • M. Goemans: Lecture Notes on On-Line Algorithms. ftp://theory.lcs.mit.edu/pub/classes/18.415/notes-online.ps
  • D. Kozen: The design and Analysis of Algorithms. Springer, 1992.
  • N. Lynch: Distributed Algorithms. Morgan Kaufmann, 1996.
  • R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
  • R. Niedermeier: Parameterized algorithm script from the University of Tübingen. http://www-fs.informatik.uni-tuebingen.de/lehre/ss99/paal.html
  • C.H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
  • U. Schöning: Algorithmics. Spectrum Academic Publishing House, 2001.
  • A. Lenstra: Integer factoring. Designs, Codes and Cryptography 19, 101-128 (2000).