1. komponenta

Vrsta nastave	Ukupno
Predavanja	45
Auditorne vježbe	30

* Opterećenje je izraženo u školskim satima (1 školski sat = 45 minuta)

CILJ KOLEGIJA:
Studente osposobiti za:
- analizu vremenske i prostorne složenosti zadanog algoritma;
- efikasnu implementaciju naprednijih klasičnih algoritama i složenijih struktura podataka;
- matematičko modeliranje problema iz stvarnog svijeta (tipično, u terminima teorije grafova ili kombinatorne optimizacije), uz odabir ili dizajn odgovarajućeg algoritma za rješavanje te određivanje njegove složenosti;
- samostalno osmišljavanje novih struktura podatka i algoritama pogodnih za rješavanje novih, nestandardnih problema.

NASTAVNI SADRŽAJI:
1. Složenost algoritama. Problemi i algoritmi; vremenska i prostorna složenost. Klase složenosti: P i NP, NP-potpunost. Analiza složenosti algoritama: rekurzivni algoritmi; amortizirana analiza algoritama.
2. Sortiranje. Pregled klasičnih algoritama za sortiranje. Sortiranje u linearnom vremenu. Pronalaženje i-tog elementa i medijana skupa.
3. Stabla i hrpe. Fenwickova struktura i intervalna stabla. B-stabla. Splay stabla. Fibonaccijeva hrpa. Struktura disjunktnih skupova.
4. Algoritmi na grafovima. Pretraživanje u dubinu i širinu. Razapinjuća stabla. Algoritmi za najkraće puteve u grafu. Algoritmi za maksimalni protok u grafu.
5. Odabrani klasični algoritmi. Pretraživanje u stringu. Algoritmi računalne geometrije.
6. Randomizirani i online algoritmi. Motivacija i primjeri randomiziranih algoritama. Analiza randomiziranih algoritama. Online algoritmi i pojam kompetitivnosti.

1. Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, MIT Press, 2022.
2. Randomized Algorithms, R. Motwani, P. Raghavan, Cambridge University Press, 1995.
3. Algorithms, R. Sedgewick, Addison-Wesley Professional, 2011.
4. The Algorithm Design Manual, S. S. Skienna, Springer, 2020.
5. Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms, J. Hromkovič, Springer-Verlag, 2005.

Obavezni predmet - Redovni Studij - Računarstvo i matematika