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

Prvi domaći zadataka: Osmosmerka, Karte, Zadovoljivost jednakosti

15.12.2024.

Domaće zadatke radite lokalno. Dogovorićemo se za predavanje radova u toku semstra.

15.12.2024.

Srećan početak semestra.

07.10.2024.

§ Č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::array; std::vector; std::list; std::queue; std::priority_queue; std::map; std::unordered_map std::set; std::unordered_set

09.10.2024.

02. Napredne strukture podataka

Prefiksno drvo (Trie). Disjunktni skupovi (Union-Find).
Najveći zajednički prefiks; Autocomplete; Složene reči; Max XOR; Osvoji region; Odnosi

16.10.2024.

03. Napredne strukture podataka

Segmentno drvo. Fenvikovo drvo.
Berza; Funkcije; Maksimalan proizvod; Broj inverzija; Karte; Temperatura

24.10.2024.

04. Algebarski algoritmi

Euklidov algoritam. Eratostenovo sito. Faktorizacija. Ojlerova funkcija.
Prost trougao; Dopuna do punog kvadrata; Proizvodi potpuni kvadrati; Zbir prostih prost; Ojlerova funkcija; Bilijar iz ćoška

01.11.2024.

05. Algebarski algoritmi

Prošireni Euklidom algoritam. Modularni inverz. Kineska teorema o ostacima. RSA kriptosistem.
Torta; Modularni inverz; Kineska teorema; RSA napad

08.11.2024.

06. Algoritmi teksta

Pronalaženje uzorka u tekstu. Heširanje niski. Rabin-Karpov algoritam.
Heširanje niski (grupa zadataka); Svi različiti; ASCII umetnost

15.11.2024.

07. Algoritmi teksta

Z algoritam. KMP algoritam. Manačerov algoritam.
Nula XOR; Dopuna do palindroma; Broj palindroma; Cirkularna niska

22.11.2024.

08. Geometrijski algoritmi

Osnovni geometrijski algoritmi. Ray casting. Konstrukcija prostog mnogougla.
[geo.cpp]; Pripadnost tačke trouglu; Kolizija pravougaonika; Ribice [ray_casting.py]; Prost mnogougao [polar_sort.py]

29.11.2024.

09. Geometrijski algoritmi

Konveksni omotač. Tačka u konveksnom omotaču. Pronalaženje konveksnog omotača: Gramov algoritam i algoritam pakovanja poklona.
Pripadnost tačke konveksnom mnogouglu; Obim omotača; Galsko selo

06.12.2024.

10. Grafovski algoritmi

Reprezentacija grafova. Pretraga u dubinu. Pretraga u širinu. Topološko sortiranje. Belman-Fordov algoritam. Dijkstrin algoritam.
Korensko drvo; Autobuske rute; Broj puteva; Arbitraža dobiti; Aerodromi

06.12.2024.

11. Grafovski algoritmi

Komponente jake povezanosti: Kosaradžu algoritam. Artikulacione tačke i mostovi.
Svetiljke; Polupovezanost; Usmeravanje puteva; Uklanjanje čvorova

13.12.2024.

12. Grafovski algoritmi

Svi najkraći putevi: Flojd-Varšalov algoritam. Tranzitivno zatvorenje. Ojlerovi putevi i ciklusi. Herholcerov algoritam. Flurijev algoritam.
Igra uklanjanja čvorova; Bitke*; Lavirint; De Brujnov niz

20.12.2024.

§ Literatura

Zbirka
Konstrukcija i analiza algoritama (i smer)