Theoretical Computer Science II: Parallel Algorithms and Complexity
|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.