Courses – Fakultet tehničkih nauka u Novom Sadu

Subject: Applied algorithms (17.D0M31L)

Native organizations units: No data

Type of studies	Title
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)
Doctoral Academic Studies	Mathematics in Engineering (Godina: 1, Summer)

General information:

Category	Scientific-professional
Scientific or art field	Teorijska i primenjena matematika
Interdisciplinary	Yes
ECTS	10

Educational goal:

The educational objective of the course is to introduce the basic concepts of algorithms theory. Algorithms emerge from almost every branch of computer science, as well as engineering, biology, etc. Every problem that emerges in a scientific process and needs to be solved, requires an algorithm that processes given data and finds solution. That is why the suggested topics may be of interest from both theoretical and practical aspect.

Educational outcome:

Understanding the concept of an algorithm, as well as its main property - complexity of an algorithm. Knowing several basic complexity classes with some well-known problems as their representatives. Understanding the standard ways of dealing with difficult problems in practice, like using approximation algorithms and randomized algorithms.

Course content:

1. Introduction: Recursive functions. Turing machines, their languages. Algorithm, definition. Algorithm complexity. Space and time complexity. 2. Complexity classes: Examples of polynomial algorithms. Reductions. P=NP question. NP-complete problem, examples. coNP class. 3. Space complexity: Savich Theorem. Classes L and NL. Class Pspace, winning game strategies. Counting problems. Class #P. 4. Randomized algorithms and approximation algorithms. Probabilistic algorithms. Classes BPP, RP and coRP. Derandomization. Small sample spaces. Approximation algorithms. Class NPO. Part of the course is organized in the form of independent study and research work in the field of applied mathematics. The study and research work involves active study of primary scientific sources, organization and conduction of experiments and statistical data analysis, numerical simulations, and possibly writing a paper in the filed of applied mathematics.

Teaching methods:

Lectures. Consultations. The lectures are organized in combined form. The presentation of the theoretical part during the lecture classes is followed by the characteristic examples which contribute to better understanding of the subject matter. In addition to lectures there are regular consultations. Through research and study work the student will, on the bases of scientific journals and other relevant literature that has been studied independently, develop further understanding of the material covered in lectures. Working with the course teacher the student develops the ability to independently work on a scientific paper.

Literature:

Authors	Title	Year	Publisher	Language
U. Schöning<\eng>	Theoretische Informatik kurzgefaßt<\eng>	1995	Spektrum Akademischer Verlag GmbH, Berlin<\eng>	German
Sipser, M.	Introduction to the Theory of Computation	2006	Thomson Course Technology, Boston	English
M. Atallah<\eng>	Algorithms and theory of computation hanbook<\eng>	1999	CRC Press, London<\eng>	English