252-0209-00L  Algorithms, Probability, and Computing

Semester Autumn Semester 2017
Lecturers E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
Periodicity yearly course
Language of instruction English



Catalogue data

Abstract Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction).
Objective Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Lecture notes Will be handed out.
Literature Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest;
Randomized Algorithms by R. Motwani und P. Raghavan;
Computational Geometry - Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.

Performance assessment

Performance assessment information (valid until the course unit is held again)
Performance assessment as a semester course
ECTS credits 8 credits
Examiners E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
Type session examination
Language of examination English
Course attendance confirmation required No
Repetition The performance assessment is only offered in the session after the course unit. Repetition only possible after re-enrolling.
Mode of examination written 180 minutes
Additional information on mode of examination There will be a written midterm exam and a written final exam. Script or any other supplementary material for either exam is not permitted. The grade of the midterm exam amounts to 20% and the grade of the final exam to 60% of the final grade. Extra reading material will be distributed and two special graded assignments - related to this reading material - handed out during the course. The grade of the special assignments amounts to 20% of the final grade.
Written aids Keine Hilfsmittel erlaubt.
This information can be updated until the beginning of the semester; information on the examination timetable is binding.

Learning materials

 
Main link Information
Only public learning materials are listed.

Courses

Number Title Hours Lecturers
252-0209-00 V Algorithms, Probability, and Computing 4 hrs
Mon 13-15 CAB G 51 »
Tue 14-16 CAB G 51 »
E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
252-0209-00 U Algorithms, Probability, and Computing 2 hrs
Wed 13-15 CAB G 56 »
13-15 CHN D 44 »
16-18 CAB G 52 »
E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
252-0209-00 A Algorithms, Probability, and Computing
Project Work, no fixed presence required.
1 hrs E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer

Restrictions

There are no additional restrictions for the registration.

Offered in

Programme Section Type
Computer Science Bachelor Major in Theoretical Computer Science O Information
Computer Science Bachelor Major: Theoretical Computer Science O Information
Computer Science Teaching Diploma Part 2 W Information
Mathematics Bachelor Core Courses: Applied Mathematics and Further Appl.-Oriented Fields W Information