Theory of Algorithms | Faculty of Technical Sciences

Subject: Theory of Algorithms (17.IFE211)

Native organizations units: Chair of Applied Computer Science

Type of studies	Title
Undergraduate Academic Studies	Information Engineering (Year: 1, Semester: Summer)

General information:

Category	Theoretical-methodological
Scientific or art field	Applied Computer Science and Informatics
ECTS	5

The overall education goal of course is development of algorithmic culture in todays engineers, as an important part of general engineering culture. The particular education goals are development of student’s ability to ?) understand basic concepts from Theory of Algorithms and Computational Complexity disciplines, b) determine algorithmic hardness of the problems, c) chose algorithmic technique which is adequate to the hardness of the problem at hand and d) apply adequate algorithms in solving problem of interest.

The basic education outcomes are understanding and determination of algorithmic hardness of the problem and the complexity of algorithms, as well as independent algorithmic solving of engineering problems of interest.

Introduction to the Theory of Algorithms and Computational Complexity. Determination of algorithmic hardness of the problem. Reductions among problems. Asymptotic notation, time and space complexity. Basic complexity classes. Types of algorithms. Greedy, divide-and-conquer algorithms, breadth and depth first search, dynamic programming, branch-and-bound algorithms. Randomized and probabilistic algorithms. Parameterized and approximation algorithms. Algorithmic heuristics and meta-heuristics. ??thematical programming. Single- and multi-objective optimization algorithms. Parallel and distributed algorithms.

Lectures. Exercises and computer lab exercises. Consultation. On lectures, students become familiar with general algorithmic techniques, which are adequate in solving problems of different algorithmic hardness. Lectures are followed with adequate example problems on exercises and in computer lab, which helps in understanding course topics and material. Besides lectures and exercises, consultations with students are regularly held.

Authors	Title	Year	Publisher	Language
G. Ausiello, P. Crescenzi, V. Kann, Marchetti-sp, Giorgio Gambosi, Alberto M. Spaccamela	Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties	1999	Springer	English
R. Sedgewick, K. Wayne	Algorithms (4th Edition)	2011	Pearson Education, Inc.	English
Cormen, T.H. et al.	Introduction to Algorithms	2009	MIT Press, Cambridge	English
Christos H. Papadimitriou	Computational Complexity	1995	Addison Wesley Longman	English
Kozen, Dexter, C	Theory of computation	2006	Springer	English
Zbigniew Michalewicz, David B. Fogel	How to Solve It: Modern Heuristics	2010	Springer, 2nd Rev&Ext. edition	English