252-0417-00L  Randomized Algorithms and Probabilistic Methods

SemesterAutumn Semester 2018
LecturersA. Steger
Periodicityyearly recurring course
Language of instructionEnglish



Courses

NumberTitleHoursLecturers
252-0417-00 VRandomized Algorithms and Probabilistic Methods3 hrs
Tue13:15-14:00CAB G 51 »
Thu08:15-10:00CAB G 51 »
18.09.13:15-14:00HG E 1.1 »
A. Steger
252-0417-00 URandomized Algorithms and Probabilistic Methods2 hrs
Tue16:15-18:00CAB G 51 »
16:15-18:00ML H 41.1 »
A. Steger
252-0417-00 ARandomized Algorithms and Probabilistic Methods
Project Work, no fixed presence required.
2 hrsA. Steger

Catalogue data

AbstractLas 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
Learning objectiveAfter 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.
ContentRandomized 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.
Lecture notesYes.
Literature- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)
- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits8 credits
ExaminersA. Steger
Typeend-of-semester examination
Language of examinationEnglish
RepetitionThe performance assessment is only offered at the end after the course unit. Repetition only possible after re-enrolling.
Additional information on mode of examinationExercises 30% to the final grade (compulsory continuous performance assessments): 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.

Learning materials

No public learning materials available.
Only public learning materials are listed.

Groups

No information on groups available.

Restrictions

There are no additional restrictions for the registration.

Offered in

ProgrammeSectionType
CAS in Computer ScienceFocus Courses and ElectivesWInformation
Data Science MasterCore ElectivesWInformation
Doctoral Dep. of Information Technology and Electrical EngineeringDoctoral and Post-Doctoral CoursesWInformation
Computer Science TCSpecialized Courses in Respective Subject with Educational FocusWInformation
Computer Science Teaching DiplomaSpec. Courses in Resp. Subj. w/ Educ. Focus & Further Subj. DidacticsWInformation
Computer Science MasterFocus Core Courses Theoretical Computer ScienceWInformation
Computer Science MasterCore Focus Courses General StudiesWInformation
Mathematics BachelorAuswahl: Theoretical Computer ScienceWInformation
Mathematics MasterAuswahl: Theoretical Computer Science, Discrete MathematicsWInformation
Computational Science and Engineering BachelorElectivesWInformation
Computational Science and Engineering TCFurther Subject DidacticsWInformation
Computational Science and Engineering MasterElectivesWInformation