## 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:

- Lecture notes
- S. Baase: Computer Algorithms. Introduction to Design and Analysis.
- A. Aho, J. Hopcroft, J. Ullman: The Design and Analysis of Computer
Algorithms
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to
Algorithms