Course: Algorithms and Complexity 1

« Back
Course title Algorithms and Complexity 1
Course code KMI/ALS1
Organizational form of instruction Lecture + Exercise
Level of course Master
Year of study 1
Semester Winter
Number of ECTS credits 5
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
  • Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
  • Konečný Jan, RNDr. Ph.D.
Course content
The course is devoted to advanced analysis of search algorithms and data structures. Binary search trees -- randomly grown trees, average case complexity, average height, Catalan numbers; Fibonacii trees, balanced trees; Hashing -- average case complexity, universal hashing, perfect hashing; Quicksort -- linear selection of median, average case complexity; Tries, statis and dynamic R-trees, M-trees, kD-trees; Pagerank.

Learning activities and teaching methods
Lecture, Demonstration
Learning outcomes
The students become familiar with selected advanced concepts of algorithms and complexity.
2. Comprehension. Understand basic concepts of algorithms and complexity.

Assessment methods and criteria
Oral exam, Written exam

Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
Recommended literature
  • Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. (2001). Introduction to Algorithms. Second Edition.. MIT Press.
  • Elden, L. (2007). Matrix Methods in Data Mining and Pattern Recognition. SIAM.
  • Knuth D. E. (1973). The Art of Computer Programming, Volumes I & III. Addison-Wesley.
  • Manolopoulos Y., et al. (2005). R-Trees: Theories and Applications.. Springer.
  • Skiena S. S. (1998). The Algorithms Design Manual. Springer, New York.

Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Science Teaching Training in Computer Science for Secondary Schools (1) Pedagogy, teacher training and social care 1 Winter
Faculty of Science Applied Computer Science (1) Informatics courses 1 Winter
Faculty of Science Bioinformatics (1) Informatics courses 1 Winter
Faculty of Science Computer Science (2015) Informatics courses 1 Winter