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