Algorithm and Complexity


Algorithms are the computational recipes to solve well-stated problems - Algorithm complexity is concerned with the computational resources - such as time and memory - required by algorithms in order to achieve their purpose - It allows the categorization of algorithms into ―good‖ or ―bad‖ - Problem complexity - on the other hand, is concerned with the distinction between "tractable" problems - that we can solve with reasonable amount of resources - and "intractable" problems - that are beyond the power of existing - or even conceivable – algorithms - Tractable problems are further classified into ―easy‖ problems and ―not so easy‖ problems depending on whether ―good‖ or ―bad‖ algorithms exist for their solution - The course treats all necessary introductory material as well as advanced topics - Specifically it covers topics on algorithm - algorithm complexity (asymptotic and average) - data structures (stack – queue - binary tree - heap) - graphs and networks - graph search (depth first search - breadth first search - strongly connected components)- shortest paths – maxflow – sorting - problem classification (P – NP - NP-complete - NP-hard) - polynomial problem transformations - branch and bound - discrete dynamic programming - approximate schemes - pseudopolynomial algorithms - heuristics and metaheuristics.

Credit Units (ECTS): 
Α2, 0856