SUBJECT
Title
Design and Analysis of Algorithms
Type of instruction
lecture+practical
Level
Master
Faculty
Part of degree program
Credits
2+2+1
Recommended in
Semester 1
Typically offered in
Autumn semester
Course description
Stable matching. Gale-Shapley algorithm. Divide and conquer algorithms. Mergesort. Counting inversions. Closest pair of points. Dynamic programming. Sequence alignment. Knapsack, subset sum and change-making problems. Greedy algorithms. Scheduling problems. Clustering. Approximation algorithms. Load balancing problem. Center selection problem. Randomized algorithms. Quicksort. Quickselect. Karger’s global minimum cut algorithm.
Readings
Compulsory readings:
- J. Kleinberg, É. Tardos: Algorithm Design. Addison-Wesley, 2006.
Recommended readings:
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Second Edition. The MIT Press, 2001.