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