Design and Analysis of Algorithms

Dr. Heinrich Rolletschek

September 17, 2014

1 Time and place:

Thursday, 8:30-10:00, K 009D, beginning October 9.

2 Entry requirements:

Knowledge of some ALGOL-like programming language, some elementary knowledge in the area of analysis.

3 Assessment/Examination:

Written or oral exam.

4 Course aims:

Students should get acquainted with a number of typical algorithms in various areas of mathematics, with principles underlying the design of such algorithms, and with methods for complexity analysis.

5 Course description:

Algorithms in various areas of mathematics are presented and their complexity is investigated. The course is organzied along these areas rather than along general principles in the design of algorithms (like recursion or dynamic programming). Such principles are dealt with when they are applied. Except for chapter 5, the emphasis is on topics not covered by other RISC-courses; in particular no advanced topics from Computer Algebra are dealt with. The topics covered by the individual chapters are: (1) General remarks about algorithms and complexity; (2) sorting algorithms; (3) graph algorithms and algorithms dealing with relations; (4) string matching; (5) arithmetic.

6 Literature: