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

Type of studies	Title

General information:

Category	Theoretical-methodological
Scientific or art field	Electronics
Interdisciplinary	No
ECTS	5

Educational goal:

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

Educational outcome:

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

Course content:

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.

Teaching methods:

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

Literature:

Authors	Title	Year	Publisher	Language
L. Novak	Algoritmi i njihova složenost - skripte	2007	FTN Novi Sad	Serbian language
Cormen, T.H. et al.	Introduction to Algorithms	2009	MIT Press, Cambridge	English
Christos H. Papadimitriou	Computational Complexity	1994	Addison Wesley Longman	English