Syllabus for |
|
| TMS081 - Randomized algorithms |
| |
| Owner: TM |
|
|
5,0 Credits (ECTS 7,5) |
| Grading: TH - Five, Four, Three, Not passed |
| Level: C |
|
Department: 11 - MATHEMATICAL SCIENCES
|
Teaching language: English
| Course module |
|
Credit distribution |
|
Examination dates |
|
Sp1 |
Sp2 |
Sp3 |
Sp4 |
|
No Sp |
| 0101 |
Examination |
5,0 c |
Grading: TH |
|
|
|
|
5,0 c
|
|
|
|
Contact examiner, |
31 Aug 2007 am V |
In programs
TM Teknisk matematik, Year 2 (elective)
EMMAS MSc PROGR IN ENGINEERING MATHEMATICS, Year 1 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (elective)
TITEA SOFTWARE ENGINEERING, Year 3 (elective)
Examiner:
Professor
Olle Häggström
Eligibility:
For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.
Course specific prerequisites
A basic course on probability or mathematical statistics, plus some programming 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. The lectures will cover
Mathematical foundations, including probabilistic methods, Markov chains, and some game theory.
Randomized algorithms for, e.g., sorting, Monte Carlo integration, stochastic simulation, approxi-mate counting, and various combinatorial and/or geometrical optimization problems.
Analysis of the complexity of randomized algorithms.
A large part of the course consists of a project, where the sutdents have the opportunity to apply the above to some concrete application, or to deepen their theoretical knowledge in some specific direction (or both!).
Literature
The lectures notes "Finite Markov Chains and Algorithmic Applications" by O. Häggström.
Examination
Presentation of the project, plus a written take-home exam.