Oblikovanje i analiza algoritama --- domaće zadaće i seminarske teme (2011/2012)


Zadnja promjena: 18.01.2012. u 12:56.


Domaće zadaće:


Seminarske teme: Kako se bira tema?

Zadnji rok za prijavu seminara (iza toga smatram da idete na 2. kolokvij):  utorak, 13. prosinca 2011. u 24 sata.

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

Termin za prezentacije prije kolokvija (max. 10 seminara po terminu) --- u vrijeme (i nakon) zadnjeg predavanja:

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. Maksimalni element skupa točaka (višedimenzionalni ``podijeli pa vladaj'')   (Ivan Stojić, 13. siječnja 2012.)
  2. Traženje raspona u skupu točaka (višedimenzionalni ``podijeli pa vladaj'')   (Andrija Štajduhar, 20. prosinca 2011.)
  3. Heapsort (sortiranje)   (Miro Antonijević, 20. prosinca 2011.)
    • Lit.:   JS 133--149 (pdf, 1058 kB),   CLR 140--152 (140--180),   KN3.
  4. Generalizirani Heapsort (sortiranje)   (Josip Grgurica, 13. siječnja 2012.)
  5. Sortiranje prebrajanjem i Radix Sort (sortiranje)   (Davor Mas, 20. siječnja 2012.)
    • Lit.:   JS 257--262 (pdf, 1107 kB),   CLR 172--184 (140--180),   KN3.
  6. Selekcija (izbor) i medijan   (Mario Berljafa, 20. prosinca 2011.)
    • Lit.:   JS 262--267 (pdf, 1107 kB),   CLR 185--194 (140--180).
  7. Presjek segmenata u ravnini (geometrija)
  8. Dijametar skupa točaka (geometrija)   (Melkior Ornik, 20. prosinca 2011.)
  9. Najdulji zajednički podniz (dinamičko programiranje)
  10. Svi najkraći putevi u grafu --- rekurzivno (dinamičko programiranje)
    • Lit.:   CLR 550--558 (550--578).
  11. Svi najkraći putevi u grafu --- Floyd--Warshall (dinamičko programiranje)   (Marko Božić, 20. prosinca 2011.)
  12. Svi najkraći putevi u grafu --- Johnson za šuplje grafove (dinamičko programiranje)
    • Lit.:   CLR 565--570 (550--578).
  13. Rabin--Karp algoritam (pretraživanje teksta)   (Sven Majerić, 20. prosinca 2011.)
    • Lit.:   JS 371--379 (pdf, 2519 kB),   CLR 857--862 (853--885).
  14. Knuth--Morris--Pratt algoritam (pretraživanje teksta)   (Lovro Rožić, 20. prosinca 2011.)
    • Lit.:   JS 379--391 (pdf, 2519 kB),   CLR 869--876 (853--885).
  15. Boyer--Moore--Horspool algoritam (pretraživanje teksta)
    • Lit.:   JS 392--398 (pdf, 2519 kB),   CLR 876--883 (853--885).
  16. Približno prepoznavanje uzorka (pretraživanje teksta)   (Anastasia Kruchinina, 13. siječnja 2012.)
  17. Stabilno sparivanje, stabilni brakovi (Gale--Shapley algoritam)   (Josip Matijević, 20. prosinca 2011.)
  18. Vremenski raspored intervala (``pohlepa'')   (Ivan Gavran, 20. prosinca 2011.)

Literatura po poglavljima (scan iz knjiga):

Dodatna literatura (predavanja s weba):



Stare stvari (iz ranijih godina)


Oblikovanje i analiza algoritama --- zima 2010./2011. (diplomski studij):

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

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

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