Opcioni domaći podrazumeva implementaciju (.cpp) i opis (.tex ili .md) nekog algoritma koji se nije izučavao na kursu. Pre početka javite se profesorki i meni mejlom sa ugrubim planom šta planirate da uradite. Takođe, kada završite, postavite rad na neki online repozitorijum.
Domaći zadatak: Osmosmerka, Karte, Zadovoljivost jednakosti, Suma k stepena, UpitipU, Dokazi sve formule!
Domaće zadatke radite lokalno. Dogovorićemo se za predavanje radova u toku semstra.
Srećan početak semestra.
01. Uvod u cpp
STL (engl. Standard Template Library): (i) Algoritmi; (ii) Strukture; (iii) Funktori; (iv) Iteratori.02. Napredne strukture podataka
Prefiksno drvo (Trie). Disjunktni skupovi (Union-Find).03. Napredne strukture podataka
Segmentno drvo. Fenvikovo drvo.04. Algebarski algoritmi
Euklidov algoritam. Eratostenovo sito. Faktorizacija. Ojlerova funkcija.05. Algebarski algoritmi
Prošireni Euklidom algoritam. Modularni inverz. Kineska teorema o ostacima. RSA kriptosistem.06. Algoritmi teksta
Pronalaženje uzorka u tekstu. Heširanje niski. Rabin-Karpov algoritam.07. Algoritmi teksta
Z algoritam. KMP algoritam. Manačerov algoritam.08. Geometrijski algoritmi
Osnovni geometrijski algoritmi. Ray casting. Konstrukcija prostog mnogougla.09. Geometrijski algoritmi
Konveksni omotač. Tačka u konveksnom omotaču. Pronalaženje konveksnog omotača: Gramov algoritam i algoritam pakovanja poklona.10. Grafovski algoritmi
Reprezentacija grafova. Pretraga u dubinu. Pretraga u širinu. Topološko sortiranje. Belman-Fordov algoritam. Dijkstrin algoritam.11. Grafovski algoritmi
Komponente jake povezanosti: Kosaradžu algoritam. 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.