Theoretical Computer Science I: Algorithms and Complexity
| Code | 323 |
|---|---|
| Semester | Fall |
| Class Hours - Lab Hours | 4 - 0 |
| Lecturers | Aris Pagourtzis, Stathis Zachos |
Description
Asymptotic estimation of computational complexity, criteria for algorithm selection, polynomial-time algorithms. Priority queues, binary heap, disjoint sets, union-find. Data processing (sorting, selection, search). Algorithm design techniques: divide-and-conquer, greedy, dynamic programming. Applications to graph problems: breadth first search, depth first search, minimum spanning tree, shortest paths, max flow and min cut. Randomized and approximation algorithms. Computability and computational complexity. Complexity classes and reductions. The classes of P and NP, NP-completeness. Space complexity and classes. Oracles and hierarchies.