Oblikovanje i analiza algoritama — seminarske teme (2009/10)


Zadnja promjena: 17.01.2010. u 21:11.  (31. svibnja 2018.)


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:

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 (posebno, knjige), pogledajte uputu malo niže!
Napomena: Kod skidanja literature potrebna je autorizacija = "kolegijsko" korisničko ime (login) i lozinka (password).


Popis tema po područjima


Seminarske teme:

  1. Problem popločavanja (tiling) (``podijeli pa vladaj'')
  2. Sortiranje polja --- Mergesort (``podijeli pa vladaj'')
    • Lit.:   JS 219--225 (pdf, 962 kB),   CLR 13--16,   KN3.
  3. Najbliži par točaka (``podijeli pa vladaj'', geometrija)
    • Lit.:   JS 225--232 (pdf, 962 kB),   CLR 908--912,   ALS 192--195.
  4. Sortiranje prebrajanjem i Radix Sort (sortiranje)
    • Lit.:   JS 257--262 (pdf, 1107 kB),   CLR 172--184 (140--180),   KN3.
  5. Selekcija (izbor)
    • 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)
    • Lit.:   CLR 527--532, 532--536,   ALS 232--239.
  9. Najdulji zajednički podniz (dinamičko programiranje)
  10. Ulančano množenje matrica (dinamičko programiranje)
  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. Stabilno sparivanje, stabilni brakovi (Gale--Shapley algoritam)
  14. Vremenski raspored intervala (``pohlepa'')
  15. Vremenski raspored intervala s težinama (dinamičko programiranje)



Literatura