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

T-79.5204 Combinatorial Models and Stochastic Algorithms (6 cr) P

Spring 2007

The course T-79.5204 replaces the course T-79.250 Combinatorial Models and Stochastic Algorithms .

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] [Links]

Previous years (as T-79.250): [Spring 2005] [Spring 2003]

Current

  • [2 May 2007] Scanned solutions for tutorial sessions 10-12 now available.
  • [26 Apr 2007] The lectures and tutorials for this Spring are over; many thanks for your active participation. The Spring exam for the course is scheduled for Thu 10 May, 1-4 p.m., in DCSE Lecture Hall T2. Please verify the time and place from the DCSE department exam schedule, and remember to register for the exam via TOPI. Also, remember to provide feedback on the course via the department's course feedback system. The electronic questionnaires were opened on Wed 25 Apr and will close on Wed 23 May.
  • [22 Apr 2007] Full updated set of lecture notes available.
  • [13 Apr 2007] Last lecture on Thu 19 Apr. Last tutorial session on the following week, Thu 26 Apr.
  • [20 Mar 2007] Deadline for submitting topics of programming assignments postponed to Wed 4 April.
  • [1 Mar 2007] Deadlines for programming assignment fixed; for details see below.
  • [22 Feb 2007] Note that there are only four problems in the problem set for tutorial 6 (Mar 1), rather than six as originally announced.
  • [24 Jan 2007] Hardcopy versions of the lecture notes (from 2005) now available for purchase via Edita.
  • [7 Jan 2007] First lecture Tue 16 Jan 10-12, room TB353.
  • [7 Jan 2007] Registration for the course is by TOPI.

General

  • Lectures: Pekka Orponen 16 Jan - 26 Apr, Tue & Thu 10-12 room TB353.
  • Tutorials: Pekka Orponen, Thu 12-14, room TB353.
  • Examination: Scheduled for Thu 10 May 13-16 T2. (Please verify the time and place from the DCSE department exam schedule.)
  • Registration by TOPI.
  • Prerequisites: First two years' mathematics courses including introductory probability theory (e.g. Mat-1.2600/Mat-2.090), and programming skills (e.g. T-106.1200/T-106.230). Familiarity with stochastic processes (Mat-2.111), discrete mathematics (Mat-1.2991/Mat-1.128), algorithm design (T-106.4100/T-106.410) and computational complexity theory (T-79.5103/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, on paper or per e-mail) to P.O. between 13 March and 4 April; if you have difficulty in picking a problem, come discuss alternatives after class or during office hours (Tue 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 Fri 1 June. You are free to choose whatever programming language and environment is most suitable for the task.
  • Course brochure: Finnish

Course contents (tentative)

  • 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
      Combinatorial phase transitions
      Structure of fitness landscapes [optional]

Lecture schedule

  • Week 1. Markov chains: structure; recurrent and transient states; regular chains; stationary distribution. Notes.
  • Week 2. Markov chains: existence and uniqueness of stationary distribution for regular chains; convergence; transients; reversibility. Notes.
  • Week 3. Markov chains: MCMC sampling; convergence rate, conductance. Notes.
  • Week 4. Markov chains: conductance and second eigenvalue; canonical paths. Notes.
  • Week 5. Markov chains: coupling; the Propp-Wilson algorithm. Notes.
  • Week 6. Combinatorial models: elements of statistical mechanics; the Ising model, spin glasses. Notes.
  • Week 7. Combinatorial models: neural networks, NK networks, Erdös-Rényi random graphs. Notes.
  • Week 8. Combinatorial models: Erdös-Rényi random graphs (threshold functions). Notes.
  • Week 9. Combinatorial models: Erdös-Rényi random graphs (phase transition), nonuniform random graphs. Notes. Slides from a talk on networks at the Finnish Science Days, Jan. 2005 (in Finnish).
  • Week 10. Algorithms: simulated annealing, approximate counting. Notes.
  • Week 11. Algorithms: MCMC estimation. Notes.
  • Week 11 1/2. Algorithms: Genetic algorithms (not part of the course in 2007). Notes.
  • Week 12. Algorithms: Combinatorial phase transitions, statistical mechanics of K-SAT. Notes. Slides from a talk on phase transitions in local search at the University of Helsinki, Nov. 2005.

Lecture notes from 2007

Typeset lecture notes from the Spring 2007 instalment of the course are available online in both one page per sheet and two pages per sheet format. This is a revised edition of the notes that were most kindly typeset and made available by Vesa Hölttä in Spring 2003, and then first updated in Spring 2005.

Tutorial problems

Problem sets will be available here as the course progresses. The problems are likely to be largely the same as in Spring 2005.

Exams

The exams are "open book": you may bring with you a copy of the lecture notes, plus the tutorial problem sets and their solutions. Also a standard non-programmable function calculator is permitted, but no other material or devices.

Problem sets from previous instalments of the course:

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.
      H. H. Hoos, T. Stützle, Stochastic Local Search: Foundations and Applications. Morgan Kaufmann (Elsevier), Amsterdam, 2005.
      W. Michiels, E. Aarts, J. Korst, Theoretical Aspects of Local Search. Springer-Verlag, Berlin, 2006.
      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, 3rd Ed. Springer-Verlag, New York NY, 2005.
      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

    Links

    • Some really cool applets illustrating the Propp-Wilson algorithm from Jim Propp's home page.
    [TCS main] [Contact Info] [Personnel] [Research] [Publications] [Software] [Studies] [News Archive] [Links]
    Latest update: 17 October 2007. Pekka Orponen.