Andrija Urošević
Lična strana Kursevi Kontakt

Dizajn i analiza algoritama
Algoritmi i strukture podataka

§ Osnovne informacije

Predavanja:
dr Sana Stojanović Đurđević
Vežbe:
Andrija Urošević
Obaveze:
(i) Domaći zadaci: 30p. Rok za odbranu je prvo izlaženje na pismeni. Na dan pismenog ispita, ili nekoliko dana pre. Javiti putem mejla.
(ii) Pismeni ispit: 30p
(iii) Usmeni ispit: 40p

§ Obaveštenja

• Prijava ispita za ispitni rok jun1.

12.06.2024.

• Rezultati svih ispitnih rokova.

09.02.2024.

• Treći domaći je aktivan.

19.12.2023.

Nadoknada 16.12.2023. od 13č na trgu.

13.12.2023.

• Drugi domaći je aktivan.

10.12.2023.

• Prvi domaći je postavljen na petlji (ukoliko link ne radi prvo se ulogujte).

17.11.2023.

Čas u utorak 31.10.2023. se odlaže za sledeću nedelju.

30.10.2023.

Novi termin vežbi: utorkom od 13č do 15č u N201.

30.10.2023.

Prvi čas vežbi će se održati u drugoj nedelji oktobra.

05.10.2023.

§ Časovi

01. Uvod u cpp

STL (engl. Standard Template Library): (i) Algoritmi; (ii) Strukture; (iii) Funktori; (iv) Iteratori.
Ivan Drecun, Vladan Kovačević: C++ podsetnik; std::map; std::unordered_map

13.10.2023.

02. Napredne strukture podataka

Prefiksno drvo (Trie).
[trie.cpp] [prefix.cpp] [trie_sort.cpp] [max_freq_word.cpp] [max_xor.cpp] [autocomplete.cpp]

20.10.2023.

03. Napredne strukture podataka

Segmentno drvo.
[segment_tree.cpp] [composite.cpp] [inversions.cpp]

24.10.2023.

04. Algebarski algoritmi

Modularna aritmetika. Faktorizacija. Eratostenovo sito.
[mod_op.cpp] [factorization.cpp] [square.cpp] [table.cpp] [eratosthens.cpp] [num_primes.cpp]

07.11.2023.

05. Algebarski algoritami

Prošireni Euklidov algoritam. Multiplikativni inverz. Kineska teorema o ostacima. Brza Frurijeova transformacija. RSA algoritam.
[gcd.cpp] [euclid.cpp] [mul_inv.cpp] [crt.cpp] [fft.cpp] [rsa.py]

14.11.2023.

06. Algoritmi za pretragu niski

Naivni algoritam. Modifikovani naivni algoritam. Rabin-Karpov algoritam. Z algoritam.
[naive_string_matching.cpp] [all_different_string_matching.cpp] [rabin_karp.cpp] [z_algorithm.cpp]

21.11.2023.

07. Algoritmi za pretragu niski

KMP algoritam. Periodičnost niski. Palindromi. Manačerov algoritam.
[kmp.cpp] [manacher.cpp]

28.11.2023.

08. Geometrijski algoritmi

Osnovni geometrijski algoritmi. Tačka preseka pravih. Kolizija pravougaonika. Polarno sortiranje. Algoritam puštanja zraka.
[geo.cpp] [line_intersection.cpp] [rect_collision.cpp] [polar_sort.py] [ray_casting.py]

05.12.2023.

09. Geometrijski algoritmi

Konveksni omotač. Tačka u konveksnom omotaču. Pronalaženje konveksnog omotača: Iterativno, Gramov algoritam, algoritam pakovanja poklona, QuickHull.
[point_in_convex_hull.cpp] [iterative.py] [graham.cpp] [jarvis.cpp]

12.12.2023.

10. Grafovski algoritmi

Reprezentacija grafova. Pretraga u širinu. Pretraga u dubinu. Topološko sortiranje. Belman-Fordov algoritam. Dijkstrin algoritam.
[bfs.cpp] [dfs.cpp] [topological_sort.cpp] [bellman_ford.cpp] [dijkstra.cpp]

16.12.2023.

11. Grafovski algoritmi

Komponente jake povezanosti: Kosaradžu i Tardžan. Artikulacione tačke i mostovi.
[scc_kosaraju.cpp] [scc_tarjan.cpp] [articulation_points.cpp] [bridges.cpp]

16.12.2023.

12. Grafovski algoritmi

Svi najkraći putevi: Flojd-Varšalov algoritam. Tranzitivno zatvorenje. Ojlerovi putevi i ciklusi. Herholcerov algoritam. Flurijev algoritam.
[floyd_warshall.cpp] [transitive_closure.cpp] [is_euler.cpp] [is_euler_directed.cpp] [hierholcer.cpp] [fleury.cpp]

19.12.2023.

§ Literatura

Zbirka