Course: Algorithms and Complexity 3

« Back
Course title Algorithms and Complexity 3
Course code KMI/ALS3
Organizational form of instruction Lecture + Exercise
Level of course Master
Year of study not specified
Semester Winter
Number of ECTS credits 5
Language of instruction Czech, English
Status of course Compulsory, Compulsory-optional
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Course availability The course is available to visiting students
  • Motyčková Lenka, doc. Ing. CSc.
Course content
PRAM model, parallel complexity classses. Ballanced binary trees, parallel prefix-sum. Pointer jumping. Divide and conquer. Partitioning. Pipelining, 2-3 trees. Accelerated cascades. Parallel sorting and merging. Distributed graph traversal algorithms. Minimum spanning tree. Leader election. Compact routing. Byzantine agreement algorithms.

Learning activities and teaching methods
Lecture, Demonstration
Learning outcomes
The students become familiar with selected concepts of algorithms and complexity.
Comprehention: design complex parallel or distributed algorithms.

Assessment methods and criteria
Oral exam, Written exam

Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
Recommended literature
  • ANDREWS G. R. (2000). Multithreaded, Parallel, and Distributed Programming. Addison-Wesley.
  • Jaja J. (1996). Introduction to Parallel Algorithms. Addison-Wesley.
  • Lynch, N. A. (1996). Distributed Algorithms. Morgan Kaufmann.
  • Tel, G. (2001). Introduction to Distributed Algorithms. Cambridge University Press.

Study plans that include the course
Faculty Study plan (Version) Branch of study Category Recommended year of study Recommended semester
Faculty of Science Computer Science (2015) Informatics courses 2 Winter
Faculty of Science Bioinformatics (1) Informatics courses 2 Winter