Oblikovanje i analiza algoritama --- domaće zadaće i seminarske teme (2008/09)


Zadnja promjena: 30.01.2009. u 20:47.


Domaće zadaće:


Seminarske teme: Kako se bira tema?

Link na forum za kolegij za pregled izabranih tema i prijavu.

Termini za prezentacije u doba predavanja (max. 6 seminara po terminu):

Rezervni termini za prezentacije (max. 4 seminara po terminu):

Ako ne stignete napraviti seminar za neki od ovih termina, javite se prije zadnjeg termina za dogovor. Iza toga, nema spasa.

Upute za prezentaciju / izlaganje seminara:


Popis tema po područjima


Linkovi na dostupnu literaturu kod pojedinih tema isti su kao i linkovi na dnu (po poglavljima), tako da ne skidate dva puta isto.

Za navedenu literaturu koja nije dostupna ovdje, javite se u doba predavanja, konzultacija, ili po dogovoru (s nekim medijem za transport).

Seminarske teme:

  1. Najbliži par točaka (geometrija)   (Dino Malpera, 26. siječnja, ocjena: 5)
    • Lit.:   JS 225--232 (pdf, 962 kB),   CLR 908--912,   ALS 192--195.
  2. Shellsort (sortiranje)   (Antonija Malenica, 26. siječnja, ocjena: 5)
    • Lit.:   KN3.
  3. Presjek segmenata u ravnini (geometrija)
  4. Konveksna ljuska skupa točaka (geometrija)
  5. Dijametar skupa točaka (geometrija)   (Goran Ljubej, 26. siječnja, ocjena: 5)
  6. Najkraći putevi iz jednog vrha u grafu --- Dijkstra, Bellman--Ford (grafovi)
    • Lit.:   CLR 527--532, 532--536,   ALS 232--239.
  7. Najveći protok kroz mrežu --- Ford--Fulkerson, Edmonds--Karp (grafovi)   (Zoran Gaćeša, 30. siječnja, ocjena: 5)
    • Lit.:   CLR 587--600 (579--629),   ALS 419--425.
  8. Najdulji zajednički podniz (dinamičko programiranje)
  9. Ulančano množenje matrica (dinamičko programiranje)
  10. Svi najkraći putevi u grafu --- Floyd--Warshall (dinamičko programiranje)   (Jurica Bradarić, 26. siječnja, ocjena: 5)
  11. Svi najkraći putevi u grafu --- Johnson za šuplje grafove (dinamičko programiranje)
    • Lit.:   CLR 565--570 (550--578).
  12. Optimalna trijangulacija poligona (dinamičko programiranje)
    • Lit.:   CLR 320--324 (301--328).
  13. Najveća zajednička mjera --- Euklidov algoritam, binarni Euklidov algoritam   (Ksenija Hodak, 30. siječnja, ocjena: 5)
    • Lit.:   CLR 809--814, 849--850.
  14. Prosti brojevi --- provjera, Miller--Rabin test (pseudoprosti brojevi)   (Andreja Jerešić, 30. siječnja, ocjena: 5)
    • Lit.:   CLR 837--844.
  15. Faktorizacija broja na proste faktore --- Pollardova rho heuristika   (Jurica Levatić, 23. siječnja, ocjena: 5)
    • Lit.:   CLR 844--849.

Literatura po poglavljima (scan iz knjiga):



Stare stvari (iz ranijih godina)


Oblikovanje i analiza algoritama --- ljeto 2008. (preddiplomski studij):