# 252-0417-00L  Randomized Algorithms and Probabilistic Methods

 Semester Herbstsemester 2016 Dozierende A. Steger, E. Welzl Periodizität jährlich wiederkehrende Veranstaltung Lehrsprache Englisch

### Lehrveranstaltungen

NummerTitelUmfangDozierende
252-0417-00 VRandomized Algorithms and Probabilistic Methods3 Std.
 Di 13:15-14:00 CAB G 51 » Do 08:15-10:00 CAB G 51 »
A. Steger, E. Welzl
252-0417-00 URandomized Algorithms and Probabilistic Methods2 Std.
 Di 16:15-18:00 CAB G 51 »
A. Steger, E. Welzl
252-0417-00 ARandomized Algorithms and Probabilistic Methods
Project Work, no fixed presence required.
1 Std.A. Steger, E. Welzl

### Katalogdaten

 Kurzbeschreibung Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks Lernziel After this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas. Inhalt Randomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than deterministic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas. Skript Yes. Literatur - Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)

### Leistungskontrolle

 Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird) Leistungskontrolle als Semesterkurs ECTS Kreditpunkte 7 KP Prüfende A. Steger, E. Welzl Form Semesterendprüfung Prüfungssprache Englisch Repetition Die Leistungskontrolle wird nur am Semesterende nach der Lerneinheit angeboten. Die Repetition ist nur nach erneuter Belegung möglich. Zusatzinformation zum Prüfungsmodus Exercises 30% to the final grade: In week 4, 7 and 10 of the term (roughly) we will hand out a specially marked exercise, whose solution (typeset in LaTeX or similar) is due two weeks later. These solutions will be graded; the grades will each account for 10% of the final grade. End of term: written exam (180 min) accounting for 70% of the grade; open book exam: you are allowed to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.

### Lernmaterialien

 Keine öffentlichen Lernmaterialien verfügbar. Es werden nur die öffentlichen Lernmaterialien aufgeführt.

### Gruppen

 Keine Informationen zu Gruppen vorhanden.

### Einschränkungen

 Keine zusätzlichen Belegungseinschränkungen vorhanden.

### Angeboten in

StudiengangBereichTyp
CAS in InformatikFokusfächer und WahlfächerW
Doktorat Departement Informationstechnologie und ElektrotechnikLehrangebot Doktorat und PostdoktoratW
Informatik DZFachwissenschaftliche Vertiefung mit pädagogischem FokusW
Informatik LehrdiplomFachwiss. Vertiefung mit pädagogischem Fokus und weitere FachdidaktikW
Informatik MasterKernfächer der Vertiefung in Theoretical Computer ScienceW
Mathematik BachelorAuswahl: Theoretische InformatikW
Mathematik MasterAuswahl: Theoretische InformatikW
Rechnergestützte Wissenschaften BachelorWahlfächerW
Rechnergestützte Wissenschaften DZWeitere FachdidaktikW
Rechnergestützte Wissenschaften MasterWahlfächerW