1 Time and place:

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

2 Entry requirements:

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

3 Assessment/Examination:

There is a written exam on Friday, February 1, 10:15–11:45, MZ 005A. If you wish to take the exam later, contact me when you are ready.

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