Oblikovanje i analiza algoritama --- domaće zadaće i seminarske teme (2009/2010)


Zadnja promjena: 17.01.2010. u 21:11.


Domaće zadaće:


Seminarske teme: Kako se bira tema?

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

Termin za prezentacije prije kolokvija (max. 10 seminara po terminu):

Termini za prezentacije u doba kolokvija (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. Problem popločavanja (tiling) (``podijeli pa vladaj'')   (Nenad Kuren, 29. siječnja)
  2. Sortiranje polja --- Mergesort (``podijeli pa vladaj'')   (Ante Jukić, 8. siječnja)
    • Lit.:   JS 219--225 (pdf, 962 kB),   CLR 13--16,   KN3.
  3. Najbliži par točaka (``podijeli pa vladaj'', geometrija)   (Ana Ujčić, 8. siječnja)
    • Lit.:   JS 225--232 (pdf, 962 kB),   CLR 908--912,   ALS 192--195.
  4. Sortiranje prebrajanjem i Radix Sort (sortiranje)   (Tihomir Lolić, 8. siječnja)
    • Lit.:   JS 257--262 (pdf, 1107 kB),   CLR 172--184 (140--180),   KN3.
  5. Selekcija (izbor)   (Nikola Jerić, 15. siječnja)
    • Lit.:   JS 262--267 (pdf, 1107 kB),   CLR 185--194 (140--180).
  6. Presjek segmenata u ravnini (geometrija)
  7. Konveksna ljuska skupa točaka (geometrija)
  8. Najkraći putevi iz jednog vrha u grafu --- Dijkstra, Bellman--Ford (grafovi)   (Dejan Peretin, 22. siječnja)
    • Lit.:   CLR 527--532, 532--536,   ALS 232--239.
  9. Najdulji zajednički podniz (dinamičko programiranje)   (Denis Kežman, 29. siječnja)
  10. Ulančano množenje matrica (dinamičko programiranje)   (Iva Bojić, 22. siječnja)
  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)   (Josip Šumečki, 15. siječnja)
    • Lit.:   CLR 320--324 (301--328).
  13. Stabilno sparivanje, stabilni brakovi (Gale--Shapley algoritam)   (Maja Ribarić, 22. siječnja)
  14. Vremenski raspored intervala (``pohlepa'')
  15. Vremenski raspored intervala s težinama (dinamičko programiranje)

Literatura po poglavljima (scan iz knjiga):

Dodatna literatura (predavanja s weba):



Stare stvari (iz ranijih godina)


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

Oblikovanje i analiza algoritama --- zima 2008./2009. (diplomski studij):