COOR course info 2001/2002

MAS 223 Complexity and Optimisation in Operational Research

Course information, Spring 2002

The lecturers for this course are The lectures are on Thursdays, 10:00-11:00 in room PP1 (People's Palace, basement), Thursdays 12:00-13:00 in the Biology Lecture Theatre and Fridays, 13:00-14:00 in room PP1.

Course description from the Undergraduate Handbook:

The course begins with an outline of complexity theory, which gives a more precise meaning to the statement that some problems (such as minimal spanning tree) are easy to solve whereas others (such as travelling salesman) are hard. Then two methods for finding approximate solutions to hard problems (the genetic algorithm and simulated annealing) are described in detail. The course will involve running some pre-prepared computer programs but students will not be required to write programs.

Key objectives are here in a .pdf file.

Credit for the course is 10% for in-course assessment (coursework) and 90% for the final examination. The coursework will consist of six assignments which will be given out in even-numbered weeks. IMPORTANT: Unfortunately we lost the use of the red box for coursework, so could people please either bring their coursework to Dr. Stark on Friday (his office hour is 2.00 to 3.00) or put it under his door earlier on Friday.

Exercise classes

Several people have asked about exercise classes. There will be an exercise class/office hour (depending on how many people come) on Tuesdays at 10.00-11.00; come to Dr. Stark's room, G53 in the Maths building.

Course material

First week's lectures
First and second week lectures continued
Some more lectures (substantially revised 22 January) on Turing machines
Lectures on P and NP
Lectures on NP-complete problems and randomised algorithms
Peter Cameron's notes from last year are here:
Peter Cameron's notes, 25 pages in .pdf
The first half of the lectures will follow the material in these notes quite closely, but not necessarily in the same order.

Introductory lectures to part 2, pdf file, 9 pages .
Lectures on randomised algorithms and pseudo-random numbers, pdf file, 2 pages .
First lectures on Simulated Annealing, pdf file, 2 pages .
Definition and basic properties of Simulated Annealing, pdf file, 6 pages .
Convergence of the SA algorithm and running it in practice, pdf file, 10 pages .
Corrected version of the main theorem and of the irreducibility of the SA algorithm , pdf file, 1 pages .
SA applied to the Max Cut Problem , pdf file, 1 pages .
SA applied to finding independent sets in graphs, pdf file, 2 pages .
How to run the SA demos on the PC network, pdf file, 1 pages .
Biography of Metropolis
(Short) biography of Teller

Introduction to genetic algorithms, pdf file, 5 pages
Basic Genetic Algorithm, Hybridization, etc., pdf file, 10 pages
Website Tutorial on GA
Genetic Java
The GA Playground
Yahoo! GA Links
Introduction to Evolutionary Biology(with some strong opinions)
Why sex is popular
alife Fusebox Morph Lab
Floys
Richard Dawkins' alife site
Artificial Life Links

Homeworks

These are due on:
  1. Tuesday 29 January 2002 (pdf file)
    Solutions (pdf file)
  2. Tuesday 5 February 2002 (pdf file)

    3. Solutions (pdf file)
  3. Tuesday 19 February 2002 (pdf file)

    4. Solutions (pdf file)
  4. Friday 15 March 2002 (pdf file)

    5. Solutions (pdf file)
  5. Wednesday 27 March 2002 (pdf file)
    Solutions (pdf file)

Sample Exams


Last Year's Exam (pdf file)
Last Year's Specimen Exam (pdf file)

Final Examination

The final examination will take place on Friday 31 May from 10:00 - 12:00 in Arts G02.

Reading

First half of course

A standard textbook for the first half of the course is
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
But you are not required to have it.

Second half of course

For simulated annealing, (which occupies the first part of the second half of the course), see
E. Aarts and J. Korst, Simulated Annealing and Boltzman Machines, Wiley, 1989.
For genetic algorithms (which occupy most of the rest of the second half of the course), see
D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
L. Davis, Handbook of Genetic Algorithms, Van Nostrand Reinhold, 1991.