
T79.5204 Combinatorial Models and Stochastic Algorithms (6 cr) P
Spring 2007
The course T79.5204 replaces the course
T79.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 T79.250):
[Spring 2005]
[Spring 2003]
 [2 May 2007] Scanned solutions for tutorial sessions
1012 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, 14 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 1012,
room TB353.
 [7 Jan 2007] Registration for the course is by
TOPI.
 Lectures:
Pekka Orponen
16 Jan  26 Apr, Tue & Thu 1012 room TB353.
 Tutorials:
Pekka Orponen, Thu 1214, room TB353.
 Examination:
Scheduled for Thu 10 May 1316 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.
Mat1.2600/Mat2.090),
and programming skills (e.g. T106.1200/T106.230).
Familiarity with stochastic processes (Mat2.111), discrete
mathematics (Mat1.2991/Mat1.128),
algorithm design (T106.4100/T106.410) and
computational complexity theory (T79.5103/T79.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/21 page, on paper or per email) 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 1213).
The deadline for submitting your report of the work,
containing discussion of the problem and method chosen,
and your experimental results (about 35 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
 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 ProppWilson 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ösRényi random graphs.
Notes.
 Week 8. Combinatorial models:
ErdösRényi random graphs (threshold functions).
Notes.
 Week 9. Combinatorial models:
ErdösRé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 KSAT.
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.
Problem sets will be available here as the course progresses.
The problems are likely to be largely the same as in
Spring 2005.
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 nonprogrammable function calculator is permitted,
but no other material or devices.
Problem sets from previous instalments
of the course:
 General
E. Aarts, J. Lenstra (Eds.),
Local Search in Combinatorial Optimization.
John Wiley & Sons, New York, NY, 1997.
Y. BarYam,
Dynamics of Complex Systems.
AddisonWesley, Reading MA, 1997.
M. Habib, C. McDiarmid, J. RamirezAlfonsin, B. Reed (Eds.),
Probabilistic Methods for Algorithmic Discrete Mathematics.
SpringerVerlag, 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.
SpringerVerlag, Berlin, 2006.
D. L. Stein (Ed.), Lectures in the Sciences of Complexity.
AddisonWesley, 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. SpringerVerlag, 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
M. Jerrum, Counting, Sampling and Integrating:
Algorithms and Complexity.
Birkhäuser, Boston MA, 2003.
M. Jerrum, A. Sinclair,
"The Markov chain Monte Carlo method:
An approach to approximate counting and integration."
Approximation Algorithms for NPHard Problems.
(D. Hochbaum, ed.), pp. 482520. PWS Publishing, Boston MA, 1997.
A. Sinclair, Algorithms for Random Generation & Counting:
A Markov Chain Approach. Birkhäuser, Boston MA, 1993.
 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.
SpringerVerlag, New York NY, 1998.
B. Bollobás, Random Graphs, 2nd Ed.
Cambridge University Press, 2001.
R. Diestel,
Graph Theory, 3rd Ed.
SpringerVerlag, 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. 351380.
Elsevier, Amsterdam, 1995.
M. E. J. Newman,
"The structure and function of complex networks."
SIAM Review 45 (2003), 167256.
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.
SpringerVerlag, 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 ProppWilson 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.
