|
|
|
|
|
Thursday, 8:30-10:00, K 009D, beginning October 12.
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.