# Design and Analysis of Algorithms

## Dr. Heinrich Rolletschek

### September 30, 2010

Thursday, 8:30-10:00, K 001A, beginning October 7.

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

Written or oral exam.

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.

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.

- Lecture notes
- S. Baase: Computer Algorithms. Introduction to Design and Analysis.
- A. Aho, J. Hopcroft, J. Ullman: The Design and Analysis of Computer Algorithms