312.258 (17W) Mathematical Analysis of Algorithms
Overview
- Lecturer
- Course title german Mathematische Analyse von Algorithmen
- Type Lecture
- Hours per Week 2.0
- ECTS credits 4.0
- Registrations 9
- Organisational unit
- Language of instruction English
- possible language(s) of the assessment German , English
- Course begins on 02.10.2017
- eLearning Go to Moodle course
-
Remarks (english)
People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically. D. E. Knuth
Time and place
Course Information
Intended learning outcomes
After successful completion of this course, students will know methods and correspondings theorems in (analytic) combinatorics as listed in the contents section below. They will understand and will be able to prove these theorems and will be able to apply these methods to the analysis of algorithms.
Teaching methodology including the use of eLearning tools
Lecture with an emphasis on examples concerning the analysis of algorithms.
Course content
- Introduction. Example: Sorting algorithms.
- Generating Functions (Review and Advanced Techniques)
- Mellin Transform and Mellin-Perron Summation
- Singularity Analysis
- Saddle-Point Method
- Limiting Distributions (Overview)
Prior knowledge expected
Basic knowledge on generating functions is useful, a review will be given at the beginning of the course. Complex analysis is an important tool.
Literature
- R. Sedgewick and Ph. Flajolet, An Introduction to the Analysis of Algorithms (Book Site, Lecture Videos)
- Ph. Flajolet and R. Sedgewick, Analytic Combinatorics (Book Site, PDF Version, Lecture Videos)
- Ph. Flajolet, X. Gourdon, Ph. Dumas, Mellin Transforms and Aysmptotics: Harmonic Sums
Examination information
Examination methodology
Oral exam
Examination topic(s)
Contents of the lecture.
Assessment criteria / Standards of assessment for examinations
- The grade is obtained by a single oral exam (45 minutes), until November 30th, 2018.
- For the oral exam, you may bring copies of the slides of the lecture (containing formulae) and additional cheat-sheets containing formulae. How much and what you look up influences the grade.
Grading scheme
Grade / Grade grading schemePosition in the curriculum
- Master's degree programme Technical Mathematics
(SKZ: 401, Version: 13W.1)
-
Subject: Diskrete Mathematik
(Compulsory elective)
-
Mathematische Analyse von Algorithmen (
2.0h VO / 4.0 ECTS)
- 312.258 Mathematical Analysis of Algorithms (2.0h VO / 4.0 ECTS)
-
Mathematische Analyse von Algorithmen (
2.0h VO / 4.0 ECTS)
-
Subject: Diskrete Mathematik
(Compulsory elective)