Algorithms and Complexity
|Flow||L - Computer Software|
|Category||Obligatory (half flow)|
|Class Hours - Lab Hours||4 - 1|
|Lecturers||Dimitris Fotakis, Theodora Souliou (T & R Associates)|
|Links||MyCourses, Course's Website|
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++.