SUBJECT

Title

Algorithms I

Type of instruction

lecture + practical

Level

master

Faculty

Faculty of Science

Part of degree program

Mathematics MSc

Credits

2+3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description

Sorting and selection. Applications of dynamic programming (maximal interval-sum, knapsack, order of multiplication of matrices, optimal binary search tree, optimization problems in trees).

Graph algorithms: BFS, DFS, applications (shortest paths, 2-colorability, strongly connected orientation, 2-connected blocks, strongly connected components). Dijkstra’s algorithm and applications (widest path, safest path, PERT method, Jhonson’s algorithm). Applications of network flows. Stable matching. Algorithm of Hopcroft and Karp.

Concept of approximation algorithms, examples (Ibarra-Kim, metric TSP, Steiner tree, bin packing). Search trees. Amortization time. Fibonacci heap and its applications.

Data compression. Counting with large numbers, algorithm of Euclid, RSA. Fast Fourier transformation and its applications. Strassen’s method for matrix multiplication.

Readings

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, McGraw-Hill, 2002