Algorithms and Complexity

Code 3.4.3105.7
Semester 7th
Flow L - Computer Software
Category Obligatory (half flow)
Credits 5
Class Hours - Lab Hours 4 - 1
Lecturers Dimitris Fotakis, Theodora Souliou (T & R Associates)
Links MyCourses, Course's Website
Web Platform Webex


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