KMI/ALS 3 Algorithms and Complexity 3

Lecturer: Lenka Motyčková
Lecture: 2 hours/week + exercise 2 hours/week
Credits: 5
Winter semester
Form of course completion: credit course, exam

• 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.