The course gives 5.0 credit units (at Chalmers or at GU).
Instructor: Johan Tykesson (J.T.), email johant@math.chalmers.se
Email list: I maintain an email list for information pertaining to the course. If you want to be on this list, contact me (J.T.) and I will put you on the list. You can also sign up on the list on the first lecture.
Click here to download this year's home exam: ps-file and pdf-file.
Course content:
That randomization (the use of random numbers in computer algorithms)
in many situations leads to better and faster algorithms, is a
fundamental but fairly recent insight. The purpose of the course is to
communicate this insight, and to provide familiarity with randomized
algorithms and their mathematical foundations. Topics covered are
|
|
Lectures: There will be approximately 10 lectures. This year the lectures are scheduled on Tuesdays 13-15 in MVF26 and Fridays 10-12 in MVF33 in the new mathematics building.
The project homepage is here. Please note that it may be updated with more projects later!
| Lecture 1:Two basic examples of randomized algorithms: Calculation of area using the Monte Carlo Method and the Random Quicksort algorithm for sorting. These examples are not covered by the coursebook. The quick sort example was taken from the book "Randomized Algorithms" by Rajeev Motwani and Prabhakar Raghavan. | Tue | 14 March | 13.15-15.00 | MV:H11 | Lecture 2:Introduction to Markov Chains. From the book we will cover in essential pages 8-12, and do problem 2.1. | Fri | 17 March | 10.00-11.45 | MV:F33 | Lecture 3:Introduction to Markov Chains. We covered simulation of Markov chains, aperiodicity, irreducibility, and did a short introduction to stationary distribution. | Tue | 21 March | 13.15-15.00 | MV:F26 | Lecture 4:Introduction to Markov Chains: Stationary distributions: existence, uniqueness and convergence (Chapter 5). Reversible Markov chains (Chapter 6). Exercises 5.4 and 6.3 will also be solved. | Tue | 28 March | 13.15-15.00 | MV:F26 | Lecture 5:Markov Chain Monte Carlo: Introduction and the hard core model. | Fri | 31 March | 10.00-11.45 | MV:F33 | Lecture 6:Markov Chain Monte Carlo: q-coloring of graphs and Metropolis Hastings. | Tue | 4 April | 13.15-15.00 | MV:F26 | Lecture 7:Optimization using randomized algorithms: Simulated annealing. | Fri | 7 April | 10.00-11.45 | MV:F33 | Lecture 8:Approximate Counting. | Tue | 25 April | 13.15-15.00 | MV:F26 | Lecture 9:Propp-Wilson. | Fri | 28 April | 10.00-11.45 | MV:F33 | Lecture 10:Sandwiching. | Tue | 2 May | 13.15-15.00 | MV:F26 | Lecture 11:Game tree evaluation. | Fri | 12 May | 10.00-11.45 | MV:F33 | Lecture 12:Some problems from some old home exams. | Tue | 16 May | 13.15-15.00 | MV:F26 |
Some problems from the book (chapter 2) for those who has not bought it yet: PS-file and PDF-file.
Lecture notes from 2004 written by the lecturer of 2004, Fredrik Lundin. Note that my notes will differ from his, but they are both based on the book by Häggström.
Literature: Chapters 2-12 in "Finite Markov Chains and Algorithmic Applications" by Olle Häggström, one of the professors at our department. You can find it using bokfynd. The are also some available at Cremona.
Examination consists of three parts:
To pass the course, you must pass all three parts. What grade you get (3, 4 or 5 for Chalmers students, and G or VG for GU students) is determined by the score on the home exam:
The home exam will give a maximum of 20 points. The grading is then at follows. For Chalmers, you will need 8 points for a 3, 12 points for a 4 and 16 points for a 5. GU-students will need 9 points for a G and 15 points for a VG.
Here are some old home exams: 2002, 2003, 2004, 2004 with solutions.
Prerequisites: Necessary prerequisites for the course, are to have taken (and passed!)