Konstrukcija i analiza algoritama

Zvanicna stranica kursa za skolsku 2023/24.

---

Nastavno osoblje:

Nastavnici

• Filip Maric
• Vesna Marinkovic

Asistenti:

• Strahinja Stanojevic
• Andrija Urosevic
• Matija Lojovic

---

Način polaganja ispita:

• prakticni ispit od 50 poena
• teorijski test od 10 poena
• usmeni ispit od 40 poena

---

Obavestenja za skolsku 2022/23:

Spisak ispitnih pitanja iz 2022/23

---

Predavanja u skolskoj 2022/23.

1. Prefiksno drvo, disjunktni podskupovi
2. Segmentno drvo, Fenvikovo drvo, lenjo segmentno drvo
3. Reprezentacija grafa, DFS i BFS obilazak grafa
4. Topolosko sortiranje grafa. Arikulacione tacki i mostovi. Komponente jake povezanosti grafa
5. Najkraci putevi iz zadatog cvora (Dajsktrin algoritam, Belman-Fordov algoritam). Minimalno povezujuce drvo (Primov algoritam, Kruskalov algoritam)
6. Svi najkraci putevi u grafu (Flojd-Varsalov algoritam). Tranzitivno zatvorenje grafa. Ojlerovi ciklusi u grafu.
7. Modularna aritmetika. Faktorizacija. Ojlerova funkcija. Broj i zbir delilaca. Prosireni Euklidov algoritam.
8. Modularni multiplikativni inverz. FFT.
9. Hesiranje niski. Z-algoritam.
10. KMP algoritam.
11. Osnovni geometrijski algoritmi. Tacka u prostom mnogouglu. Konstrukcija prostog mnogougla.
12. Tacka u konveksnom mnogouglu. Algoritmi za konstrukciju konveksnog omotaca.

---

Dodatna literatura:

• Vesna Marinkovic, Filip Maric, Strahinja Stanojevic, Sana Stojanovic-Djurdjevic: Konstrukcija i analiza algoritama, skripta (teorija + reseni zadaci)
• Filip Maric, Vesna Marinkovic: Konstrukcija i analiza algoritama, beleske sa predavanja i vezbi
• Miodrag Zivkovic, Vesna Marinkovic: Konstrukcija i analiza algoritama, skripta
• Miodrag Zivkovic: Algoritmi