Analysis of algorithms and heuristic problem solving

Knowledge of basic algorithms and data structures.

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.
Solving linear recurrences.
Approximation algorithms.
Analysis of multithreaded and parallel algorithms.
Approximation algorithms.
Combinatorial optimization, local search, simulated annealing.
Linear programming 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
Machine learning in combinatorial optimization

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, 4th edition. MIT Press, 2022
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,
use of heuristic methods and metaheuristics, for solving complex problems,
use of population techniques and principles of evolutionary computation in optimization.

Upon passing the exam, the students will know how to analyze algorithms and their computational complexity. They will be capable to evaluate heuristic techniques for efficient solving of difficult problems and will be able to do such ana analysis on real world problem. Specifically, they will
use of methods for analysis of recursive algorithms: the substitution method and recursive-tree method,
use methods for analysis of divide-and- conquer algorithms: master theorem and Akra-Bazzi method,
probabilistically analyze the algorithms,
use the amortized analysis of algorithms,
knowing the ideas of approximation algorithms,
use and evaluate of heuristic methods and metaheuristics for solving complex problems,
use and compare population-based techniques and principles of evolutionary computation in optimization.

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)

VREŠ, Domen, ROBNIK ŠIKONJA, Marko. Preventing deception with explanation methods using focused sampling. Data mining and knowledge discovery. 2023, vol. , no. , str. 1-46
MIOK, Kristian, ŠKRLJ, Blaž, ZAHARIE, Daniela, ROBNIK ŠIKONJA, Marko. To BAN or not to BAN: Bayesian attention networks for reliable hate speech detection. Cognitive computation. Jan. 2022, vol. 14, iss. 1, str. 353-371
LAVRAČ, Nada, ŠKRLJ, Blaž, ROBNIK ŠIKONJA, Marko. Propositionalization and embeddings: two sides of the same coin. Machine learning. 2020, vol. 109, no. 7, str. 1465-1507.
KRANJC Janez, ORAČ, Roman, PODPEČAN, Vid, LAVRAČ, Nada, ROBNIK ŠIKONJA, Marko. ClowdFlows: online workflows for distributed big data mining. FGCS, 2017, vol. 68, pp. 38-58
ROBNIK ŠIKONJA, Marko. Data generators for learning systems based on RBF networks. IEEE transactions on neural networks and learning systems. May 2016, vol. 27, no. 5, str. 926-938

Celotna bibliografija je dostopna na SICRISu https://cris.cobiss.net/ecris/si/sl/researcher/8741
Complete bibliography is available in SICRIS: https://cris.cobiss.net/ecris/si/en/researcher/8741