Search programme

​Use the search function to search amongst programmes at Chalmers. The study programme and the study programme syllabus relating to your studies are generally from the academic year you began your studies.

Syllabus for

Academic year
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

In programs

TM Teknisk matematik, Year 2 (elective)
EMMAS MSc PROGR IN ENGINEERING MATHEMATICS, Year 1 (elective)
TITEA SOFTWARE ENGINEERING, Year 3 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (elective)
TDATA COMPUTER SCIENCE AND 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.


Page manager Published: Mon 28 Nov 2016.