Algorithms and Complexity
| Code | 3.4.3105.7 |
|---|---|
| Semester | 7th |
| Flow | L - Computer Software |
| Category | Obligatory (half flow) |
| Credits | 6 |
| Class Hours - Lab Hours | 4 - 1 |
| Lecturers | Dimitris Fotakis, Aris Pagourtzis, Theodora Souliou (T & R Associates), Διδάσκων ΠΔ 407/80 ή ΑΥ |
| Links | Helios, Course's Website |
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. Computability and computational complexity. Complexity classes and reductions. The classes of P and NP, NP-completeness. Space complexity and classes. Lab: a set of algorithmic problems to be solved in C/C++.