Dizajn i analiza algoritama
Algoritmi i strukture podataka

§ Osnovne informacije

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.

02. Napredne strukture podataka

Prefiksno drvo (Trie).

03. Napredne strukture podataka

Segmentno drvo.

04. Algebarski algoritmi

Modularna aritmetika. Faktorizacija. Eratostenovo sito.

05. Algebarski algoritami

Prošireni Euklidov algoritam. Multiplikativni inverz. Kineska teorema o ostacima. Brza Frurijeova transformacija. RSA algoritam.

06. Algoritmi za pretragu niski

Naivni algoritam. Modifikovani naivni algoritam. Rabin-Karpov algoritam. Z algoritam.

07. Algoritmi za pretragu niski

KMP algoritam. Periodičnost niski. Palindromi. Manačerov algoritam.

08. Geometrijski algoritmi

Osnovni geometrijski algoritmi. Tačka preseka pravih. Kolizija pravougaonika. Polarno sortiranje. Algoritam puštanja zraka.

09. Geometrijski algoritmi

Konveksni omotač. Tačka u konveksnom omotaču. Pronalaženje konveksnog omotača: Iterativno, Gramov algoritam, algoritam pakovanja poklona, QuickHull.

10. Grafovski algoritmi

Reprezentacija grafova. Pretraga u širinu. Pretraga u dubinu. Topološko sortiranje. Belman-Fordov algoritam. Dijkstrin algoritam.

11. Grafovski algoritmi

Komponente jake povezanosti: Kosaradžu i Tardžan. Artikulacione tačke i mostovi.

12. Grafovski algoritmi

Svi najkraći putevi: Flojd-Varšalov algoritam. Tranzitivno zatvorenje. Ojlerovi putevi i ciklusi. Herholcerov algoritam. Flurijev algoritam.

§ Literatura