TCS / Studies / T-79.250 Combinatorial Models and Stochastic Algorithms
Helsinki University of Technology, Laboratory for Theoretical Computer Science

T-79.250 Combinatorial Models and Stochastic Algorithms (4 cr) P

Spring 2005

Stochastic methods such as MCMC sampling, simulated annealing and genetic algorithms are currently at the forefront of approximate techniques for dealing with computationally demanding problems. This course presents these algorithms and their underlying theory, with the goal of learning to apply the methods to novel problems and achieving a broad understanding of their common foundations.

[Current] [General] [Lectures] [Tutorials] [Exams] [Literature]

Previous years: [Spring 2003]

Current

  • Grade sheet (in Finnish, pdf) available here.
  • Deadline for programming assignments extended until Mon 30 May. The assignments should be returned preferably on paper in the lecturer's mailbox in Room A357 of the Computer Science building, or else per e-mail as either a postscript or a pdf file. Remember to include also the program code used in your experiments.
  • The course exam (Wed 4 May 12-15 T1) will be "open book", i.e. you can bring with you a copy of the lecture notes, plus the tutorial problem sets and their solutions.
  • The last lecture of the course is on Fri 22 April. On Fri 29 April there will still be a tutorial session 10-12.
  • Deadlines for programming assignment fixed; for details see below.
  • Some really cool applets illustrating the Propp-Wilson algorithm from Jim Propp's home page.

General

  • Lectures: Pekka Orponen 18 Jan - 29 Apr, Tue 9-11 & Fri 12-14 room TB353.
  • Tutorials: Pekka Orponen, Fri 10-12, room TB353.
  • Examination: Wed 4 May 12-15 T1.
  • Grading: Tutorial problems, programming assignment and examination.
  • Registration by TOPI.
  • Prerequisites: First two years' mathematics courses including introductory probability theory (e.g. Mat-2.090), and programming skills (e.g. T-106.230). Familiarity with stochastic processes (Mat-2.111), discrete mathematics (Mat-1.128), algorithm design (T-106.410) and computational complexity theory (T-79.240) an asset.
  • Grading: Exam 30 points, tutorial problems 10 points, programming assignment 20 points, total 60 points.
  • Programming assignment: The goal of this task is to try out some of the sampling or optimisation methods covered in the course on a model or problem of your own choosing. Please submit a short problem description (1/2-1 page) to P.O. between 18 March and 1 April; if you have difficulty in picking a problem, come discuss alternatives after class or during office hours (Wed 12-13). The deadline for submitting your report of the work, containing discussion of the problem and method chosen, and your experimental results (about 3-5 pages plus the computer code) is Wed 25 May. You are free to choose whatever programming language and environment is most suitable for the task.
  • Course brochure (in Finnish): ps/pdf

Course contents

  • Part I: Markov Chains and Stochastic Sampling
      Finite Markov chains and random walks on graphs
      Markov chain Monte Carlo (MCMC) sampling
      Estimating the convergence rate of Markov chains
      Exact sampling with coupled Markov chains
  • Part II: Combinatorial Models
      Elements of statistical mechanics
      Models: Ising, spin glasses, neural nets, NK landscapes
      Random graphs: uniform and nonuniform
  • Part III: Stochastic Algorithms
      Stochastic local search
      Simulated annealing
      Approximate counting
      MCMC simulations
      Genetic algorithms
      Local search for satisfiability
      Combinatorial phase transitions
      Structure of fitness landscapes [optional]

Lecture schedule

  • Week 1. Markov chains: structure; recurrent and transient states; existence and uniqueness of stationary distribution for regular chains. Notes: ps, pdf.
  • Week 2. Markov chains: convergence; transients; reversibility. Notes: ps, pdf.
  • Week 3. Markov chains: MCMC sampling; convergence rate, conductance. Notes: ps, pdf.
  • Week 4. Markov chains: canonical paths; conductance and second eigenvalue; coupling. Notes: ps, pdf.
  • Week 5. Markov chains: coupling analysis of a Gibbs sampler for graph colourings; the Propp-Wilson algorithm. Notes: ps, pdf.
  • Week 6. Combinatorial models: elements of statistical mechanics; the Ising model, spin glasses, neural networks. Notes: ps, pdf.
  • Week 7. Combinatorial models: NK networks, Erdös-Rényi random graphs. Notes: ps, pdf.
  • Week 8. Combinatorial models: Erdös-Rényi random graphs (cont'd)
  • Week 9. Combinatorial models: nonuniform random graphs. Notes to appear. Slides from a talk on networks at the Finnish Science Days, Jan. 2005 (in pdf). Algorithms: simulated annealing.
  • Week 10. Algorithms: simulated annealing, approximate counting.
  • Week 11. Algorithms: MCMC estimation, genetic algorithms.
  • Week 12. Algorithms: Genetic algorithms, combinatorial phase transitions.
  • Week 13. Algorithms: local search for satisfiability. Slides Statistical mechanics of K-SAT.

Lecture notes from 2003

A typeset (ps.gz) version of the lecture notes from Spring 2003 has kindly been made available by Vesa Hölttä. Note that the ordering of topics in these notes is different from above: roughly, Parts I and II are interchanged.

Tutorial problems

Problem sets will be available here as the course progresses. The problems are likely to be largely the same as in Spring 2003; however the ordering will be different.

Exams

Problems:

Literature

  • General
      E. Aarts, J. Lenstra (Eds.), Local Search in Combinatorial Optimization. John Wiley & Sons, New York, NY, 1997.
      Y. Bar-Yam, Dynamics of Complex Systems. Addison-Wesley, Reading MA, 1997.
      M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed (Eds.), Probabilistic Methods for Algorithmic Discrete Mathematics. Springer-Verlag, Berlin, 1998.
      D. L. Stein (Ed.), Lectures in the Sciences of Complexity. Addison-Wesley, Reading MA, 1989.
  • Finite Markov chains
      E. Behrends, Introduction to Markov Chains, with Special Emphasis on Rapid Mixing. Vieweg & Sohn, Braunschweig/Wiesbaden, 2000.
      P. Brémaud, Markov Chains: Gibbs Fields, Monte Carlo Simulation, and Queues. Springer-Verlag, New York NY, 1999.
      P. G. Doyle, J. Laurie Snell, Random Walks and Electric Networks. Mathematical Association of America, Washington DC, 1984.
      O. Häggström, Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002.
      D. G. Luenberger, Introduction to Dynamic Systems: Theory, Models, and Applications. J. Wiley & Sons, New York NY, 1979.
  • Algorithmic aspects of MCMC, with emphasis on rapid mixing
  • Statistical mechanics, Ising model, spin glasses
      R. Kindermann, J. L. Snell, Markov Random Fields and Their Applications. American Mathematical Society, Providence RI, 1980.
      M. Mezard, G. Parisi, M. A. Virasoro (Eds.), Spin Glass Theory and Beyond. World Scientific, Singapore, 1987.
      L. E. Reichl, A Modern Course in Statistical Physics, 2nd Ed.. J. Wiley & Sons, New York NY, 1998.
      C. F. Stevens, The Six Core Theories of Modern Physics. The MIT Press, Cambridge MA, 1995.
  • Graph theory, random graphs, networks
      B. Bollobás, Modern Graph Theory. Springer-Verlag, New York NY, 1998.
      B. Bollobás, Random Graphs, 2nd Ed. Cambridge University Press, 2001.
      R. Diestel, Graph Theory, 2nd Ed. Springer-Verlag, New York NY, 2000.
      S. Janson, T. Luczak, A. Rucinski, Random Graphs. J. Wiley & Sons, New York NY, 2000.
      M. Karonski, "Random graphs." Handbook of Combinatorics, Vol. 1 (R. L. Graham, M. Grötschel, L. Lovász, eds.), pp. 351-380. Elsevier, Amsterdam, 1995.
      M. E. J. Newman, "The structure and function of complex networks." SIAM Review 45 (2003), 167--256.
      D. J. Watts, Small Worlds: The Dynamics of Networks Between Order and Randomness. Princeton University Press, Princeton NJ, 1999.
  • Simulated annealing, genetic algorithms
      E. Aarts, J. Korst, Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. J. Wiley & Sons, Chichester, 1989.
      L. Kallel, B. Naudts, A. Rogers (Eds.), Theoretical Aspects of Evolutionary Computing. Springer-Verlag, Berlin, 2001.
      C. R. Reeves, J. E. Rowe, Genetic Algorithms - Principles and Perspectives. Kluwer Academic, Boston MA, 2003.
      P. Salamon, P. Sibani, R. Frost, Facts, Conjectures, and Improvements for Simulated Annealing. Soc. Industrial & Applied Mathematics, Philadelphia PA, 2002.
      M. D. Vose, The Simple Genetic Algorithm. The MIT Press, Cambridge MA, 1999.
  • Combinatorial phase transitions, fitness landscapes and related topics
    [TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
    Latest update: 23 June 2005. Pekka Orponen.