Theoretical Computer Science II: Parallel Algorithms and Complexity

Code 400
Semester Spring
Class Hours - Lab Hours 4 - 0
Lecturers Dimitris Fotakis, Aris Pagourtzis, Stathis Zachos


Models of parallel computation: circuits, PRAM, BSP, map-reduce. Parallel algorithms and complexity. Design, analysis, efficiency, comparison and classification of various parallel algorithms. Lower bounds on parallel complexity. Topologies for systolic algorithms: arrays, trees, meshes, hypercubes. Complexity classes: NC, AC, TC, etc. Application of parallel methods on various problems: sorting, arithmetic operations, matrix operations, graph-theoretic problems, etc. Distributed computing: broadcast, leader election, coloring, MST, coordination, reliable computations. Mobile agents: rendezvous problems, robot gathering, black hole search, cops-and-robbers, firefighters problem, network decontamination. Pre-requisites: discrete mathematics, algorithms and complexity.