Course Instructors: Ștefan Trăuşan-Matu, Andrei Mogoş, Matei Popovici, Traian Rebedea

Discussion of the intrinsic properties of the problems from the calculability and complexity perspective and of the implications of these properties over the solving process. Introduce some problems classification methods using the difficulty of solving the problems as criteria; introduce some methods of tractable solving of the NP-hard problems. Introduce the most important techniques of the algorithm complexity analysis. Introduce the most important techniques of proving the algorithms correctness.

Syllabus:

• The measuring of the resources used by the algorithms.
• Space/time asymptotic limits for the algorithms complexity.
• General methods for the complexity analysis.
• Amortized analysis.
• Partial and total correctness.
• General methods for proving the partial correctness: deduction and induction.
• Nondeterministic algorithms, angelic complexity. Reducibility, NP-completeness.
• Cook's theorem.
• Difficulty classes (spatial and temporal) for the problems and some hierarchies for these classes.
• Case studies in problems classification.
• Approximation algorithms for NP-hard problems.
• Difficulty classes in NP-hard problems solutions approximation.
• Turing calculability.
• Decidability.