Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Theory of Algorithms and Computational Complexity (17.EM402)

Native organizations units: Department of Power, Electronic and Telecommunication Engineering

General information:

Category	Theoretical-methodological
Scientific or art field	Electronics
ECTS	5

Providing a general overview of fundamental aspects of algorithm theory and their complexity including algorithm examples from different fields of electrical and computer engineering.

The student who successfully completes this course will gain an insight in the basic concepts of algorithm theory and their complexity which include: - understanding the algorithm concept, classification of problems and algorithms, methods to prove algorithm solves each instance of the analyzed problem and complexity assessment. - compendium of problems in electrical and computer engineering

Problems and algorithmic solutions, alphabets and languages, machines and elementary operations, asymptotic notations, analysis of algorithms, algorithm techniques, concept of algorithmic complexity. Complexity classes and relations between complexity classes, reduction and completeness, P, NP and co-NP classes. Time, space, communication and energy complexity. Boolean circuit complexity. Parameterized, approximative and randomized algorithms.

Lectures; Auditory Practice; Computer Practice; Laboratory Practice; Consultations.

Authors	Title	Year	Publisher	Language
Christos H. Papadimitriou	Computational Complexity	1994	Addison Wesley Longman	English
Cormen, T.H. et al.	Introduction to Algorithms	2009	MIT Press, Cambridge	English