Konstrukcija i analiza algoritama

Zvanicna stranica kursa za skolsku 2023/24.
Nastavno osoblje:
Nastavnici Asistenti:
Način polaganja ispita:
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: