Analysis of algorithms and heuristic problem solving

Lecture topics:
Analysis of recursive algorithms: substitution method, solution for divide and conquer approach, Akra-Bazzi method.
Probabilistic analysis: definition, analysis of stochastic algorithms.
Randomization of algorithms.
Amortized analysis of algorithm complexity.
Sloving linear recurrences.
Classes P and NP: definitions, NP-completeness, standard NP-complete problems.
Reducibility and solving NP-complete problems.
Approximation algorithms.
Combinatorial optimization, local search.
Linear prfogramming for problem solving.
Metaheuristics and stochastic search: guided local search, variable neighbourhood search, and tabu search.
Population methods: genetic algorithms, particle swarm optimization, differential evolution, artificial immune systems.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 3rd edition. MIT Press, 2009
R. Sedgewick, P. Flajolet: An Introduction to the Analysis of Algorithms. Addison-Wesley, 1995
M. Gendreau, J.-Y. Potvin: Handbook of Metaheuristics, 2nd Edition. Springer, 2010.
Dodatna literatura je na razpolago v obliki znanstvenih člankov.
Additional literature is available in the form of scientific papers.

The goal of the course is the students to become acquainted with the analysis of algorithms, computational complexity and techniques for efficient solving of difficult problems, requiring optimization techniques and approximations.
General competences:
ability of critical thinking,
the ability to define, understand and solve creative professional challenges in computer and information science,
the ability of knowledge transfer and writing skills in the native language as well as a foreign language.
Subject-specific competences:
use of methods for analysis of recursive algorithms, substitution method, recursive-tree method,
use of methods for analysis of divide-and- conquer algorithms: master theorem and Akra-Bazzi method,
probabilistic analysis of algorithms,
use of amortized analysis of algorithms,
reduction of some NP-complete problems,
use of heuristic methods and metaheuristics, for solving complex problems,
use of population techniques and principles of evolutionary computation in optimization.

Knowledge and understanding:
Knowledge of several techniques and methods, used for analysis of algorithms and for solving complex optimization and combinatorial problems. The ability for analysis, synthesis and anticipation of solutions and their consequences for target problems using the scientific methodology.
Application:
The use of the presented methods on target problems from scientific and business environment. The understanding and usage of tools for analysis and solving such problems. The students are able to decide which of the presented techniques should be used for a given problem, and to develop a prototype solution.
Reflection:
The recognition and understanding of the importance of basic mathematical and statistical knowledge, the relation between theory and its application in concrete examples of analysis of algorithms and heuristic programming. Autonomy, (self) criticalness, (self) reflexivity, aspiration for quality.
Transferable skills:
The ability to receive, select and evaluate new information and a proper interpretation in a context. A self-control and ability to manage limited time when preparing, planning and implementing plans and processes. Team work, writing of reports, public presentations of the results.
Coherent mastering of basic knowledge, gained through mandatory courses, and the ability to combine the knowledge from different fields and apply it in practice.

Lectures, assignments with written and oral demonstrations and presentations, seminar works and home works, which stimulate continuous learning. The emphasis is on the continuous study and on autonomous work on assignments and seminars. Students form small project teams and autonomously solve assignments based on real-life problems. The teams describe their solutions in written reports and prepare short oral presentations. Written reports and oral presentations are graded.

Continuing (homework, midterm exams, project work)
Final (written and oral exam)
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

ROBNIK ŠIKONJA, Marko, KONONENKO, Igor. Theoretical and empirical analysis of ReliefF and RReliefF. Machine learning, ISSN 0885-6125. [Print ed.], 2003, vol. 53, str. 23-69, graf. prikazi. [COBISS-SI-ID 3813460]
ROBNIK ŠIKONJA, Marko, KONONENKO, Igor. Explaining classifications for individual instances. IEEE transactions on knowledge and data engineering, ISSN 1041-4347. [Print ed.], May 2008, vol. 20, no. 5, str. 589-600, ilustr. [COBISS-SI-ID 6528340]
PIČULIN, Matej, ROBNIK ŠIKONJA, Marko. Handling numeric attributes with ant colony based classifier for medical decision making. Expert systems with applications, ISSN 0957-4174. [Print ed.], Nov. 2014, vol. 41, no. 16, str. 7524-7535, graf. prikazi. [COBISS-SI-ID 10715732]
ROBNIK ŠIKONJA, Marko. Data generators for learning systems based on RBF networks. IEEE transactions on neural networks and learning systems, ISSN 2162-237X. [Print ed.], May 2016, vol. 27, no. 5, str. 926-938, ilustr. [COBISS-SI-ID 1536875203]
KRANJC, Janez, ORAČ, Roman, PODPEČAN, Vid, LAVRAČ, Nada, ROBNIK ŠIKONJA, Marko. ClowdFlows : online workflows for distributed big data mining. FGCS, ISSN 0167-739X. [Print ed.], 2017, vol. 68, str. 38-58. [COBISS-SI-ID 29851943]