Contents
The design and analysis of algorithms is fundamental to computer
science. In this course, we will study efficient algorithms for a
variety of very basic problems and, more generally, investigate
advanced design and analysis techniques. Central topics are some
algorithms and data structures which have not at all or not
sufficiently extensive been discussed in the undergraduate course
Informatik II. These include, but are not limited to:
- Divide and conquer: geometrical divide and conquer, fast Fourier
transform
- Randomization: randomized quicksort, probabilistic primality
testing, RSA, univeral and perfect hashing
- Amortized analysis: binomial queues, Fibonacci heaps, union-find
data structures
- Greedy procedures: shortest path, minimum spanning trees, bin
packing problem, scheduling
- Graph algorithms
- Dynamic programming: matrix chain product problem, edit distance,
longest common subsequence problem
- String matching and text compression: Knuth-Morris-Pratt
algorithm, Boyer-Moore algorithm, suffix trees, Huffman coding,
Lempel-Ziv-Welch data compression algorithm
Prerequisites
The knowledge of algorithms and data structures described in chapters 1
to 6 of the book "Algorithmen und Datenstrukturen" by Th. Ottmann und
P. Widmayer is a prerequisite for understanding the topics of this
course (see also Lecture "Informatik II").
Modules
- lecture 3 hours per term and exercise 1 hour per term, both in
English ("3V+1Ü SWS")
- ECTS: 6