Oblikovanje i analiza algoritama 2014/15

Oblikovanje i analiza algoritama — seminarske teme i seminari (2014/15)

Zadnja promjena: 20. siječnja 2015. u 22:13. (31. svibnja 2018.)

Seminarske teme su podijeljene u dvije grupe: standardne teme i poglavlja (``kolumne'') iz knjiga Jona Bentleya. Detaljni popis je malo niže.

Kako se bira tema?
- Izbor teme ide po sistemu: tko se prvi (pri)javi, njegova je!
- Realizacija prijave ide preko foruma za kolegij.
- Prije izbora teme, prvo pogledajte na forum koje teme su već izabrane. To je jedini mjerodavni popis!

ne želi

Zadnji rok za prijavu seminara (iza toga smatram da idete na 2. kolokvij): ponedjeljak, 22. prosinca 2014., u 24 sata.

Termin za prezentacije seminara --- u vrijeme zadnjeg predavanja: utorak, 20. siječnja 2015., 12--15 sati.

Upute za prezentaciju / izlaganje seminara:
- Trajanje izlaganja je 20 minuta, tj. dva seminara na sat, uz vrijeme za diskusiju (i pauze).
- Ne morate se strogo držati teksta iz literature. Poneke stvari smijete skratiti ili proširiti (na primjer, koristeći zadatke na kraju poglavlja).
- U Bentleyevim knjigama, na kraju knjige, postoje i rješenja nekih zadataka.
- Dozvoljeno (poželjno) je koristiti i dodatnu literaturu. Propisno navedite što ste koristili.
- Bitno je da cijelo izlaganje ima ``glavu, sredinu i rep''.
- Poželjna struktura prezentacije:
  - uvod --- što je problem?
  - potrebni matematički rezultati o problemu (ako treba),
  - kratki opis algorit(a)ma i složenosti,
  - ukratko o implementaciji (ako ima zanimljivih detalja),
  - opis testiranja i prikaz rezultata.

Napomena: 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!
- Kod skidanja literature potrebna je autorizacija = "kolegijsko" korisničko ime (login) i lozinka (password).

Popis tema po područjima

Standardne seminarske teme:
1. Najbliži par točaka (``podijeli pa vladaj'', geometrija)
  - Lit.: JS 225--232 (pdf, 962 kB), CLR 908--912, CLRS (33.4) 834--840, KT (5.4) 225--231, ALS 192--195.
2. Selekcija (izbor) i medijan
  - Lit.: JS 262--267 (pdf, 1107 kB), DM 111--115 (pdf, 1210 kB), CLR 185--194 (140--180), CLRS (9.2, 9.3) 160--172.
3. Presjek segmenata u ravnini (geometrija)
  - Lit.: CLR 886--898, CLRS (33.1, 33.2) 813--826, ALS 467--471 (pdf, 488 kB).
4. Konveksna ljuska skupa točaka (geometrija)
  - Lit.: CLR 898--908, CLRS (33.3) 826--833, ALS 471--474 (pdf, 488 kB).
5. Segmentirani najmanji kvadrati (dinamičko programiranje)
  - Lit.: KT (6.3) 261--266.
6. Sekundarna struktura RNA (dinamičko programiranje)
  - Lit.: KT (6.5) 272--278.
7. Poravnanje nizova (dinamičko programiranje)
  - Lit.: KT (6.6, 6.7) 278--284, 284--290.
8. Stabilno sparivanje, stabilni brakovi (Gale--Shapley algoritam)
  - Lit.: KT (1.1) 1--12, DM 4--8 (pdf, 1210 kB).
9. Vremenski raspored intervala (``pohlepa'')
  - Lit.: KT (4.1) 116--125, DM 24--26 (pdf, 1210 kB).
10. Vremenski raspored intervala s težinama (dinamičko programiranje)
  - Lit.: KT (6.1) 252--258, DM 44--47 (pdf, 1210 kB).

Poglavlja (``kolumne'') iz knjige Jona Bentleya ``Programming Pearls (2. izdanje)'':
1. Tehnike za konstrukciju algoritama, suma potpolja
  - Lit.: PP2, column 8, str. 77--86.
2. Ubrzavanje koda, binarno traženje
  - Lit.: PP2, column 9, str. 87--98.
3. Stiskanje prostora
  - Lit.: PP2, column 10, str. 99--111.
4. Sortiranje, Quicksort, ubrzanje
  - Lit.: PP2, column 11, str. 115--124.
5. Primjer problema, slučajni cijeli brojevi bez ponavljanja
  - Lit.: PP2, column 12, str. 125--132.
6. Traženje, implementacija konačnog skupa cijelih brojeva
  - Lit.: PP2, column 13, str. 133--146.
7. Hrpe, implementacija, heapsort
  - Lit.: PP2, column 14, str. 147--159.
8. Stringovi, riječi, fraze, tekst
  - Lit.: PP2, column 15, str. 161--173.

Poglavlja (``kolumne'') iz knjige Jona Bentleya ``More Programming Pearls'':
1. Uzorak briljantnosti, slučajni brojevi, slučajne permutacije
  - Lit.: More_PP, column 13, str. 139--145.
2. Rođenje drobilice brojeva, euklidska udaljenost, računanje korijena
  - Lit.: More_PP, column 14, str. 147--158.
3. Izbor (selekcija), k-ti po veličini, medijan
  - Lit.: More_PP, column 15, str. 159--170.

Literatura

Literatura po poglavljima (scan iz knjiga):
- JS 133–162 (dio 3. poglavlja): Strukture podataka, Heapsort (pdf, 1058 kB)
- JS 213–238 (5. poglavlje): ``Podijeli pa vladaj'' algoritmi (pdf, 962 kB)
- JS 239–270 (6. poglavlje): Sortiranje i pretraživanje (pdf, 1107 kB)
- JS 275–295 (dio 7. poglavlja): Pohlepni algoritmi — Kruskal, Prim (pdf, 788 kB)
- JS 323–365 (8. poglavlje): Dinamičko programiranje (pdf, 1261 kB)
- JS 367–428 (9. poglavlje): Pretraživanje teksta (pdf, 2519 kB)
- ALS 203–226 (7. poglavlje): Dinamičko programiranje (pdf, 6097 kB)
- ALS 462–480 (18. poglavlje): Geometrijski algoritmi (pdf, 488 kB)

Dodatna literatura (predavanja s weba):
- DM08 1–137: David M. Mount, Design and Analysis of Computer Algorithms, Spring 2008 (pdf, 1210 kB)

Kako do knjiga? Za izravni link na knjigu treba spojiti tri stvari:
- na prvi dio "http://degiorgi.math.hr/oaa/oaa_lit/"
- treba dodati ime s ekstenzijom
  - "ALS" (pdf, 21552 kB)
  - "CLR" (pdf, 54952 kB)
  - "CLRS" (pdf, 13081 kB) (novije izdanje CLR, stranice i sadržaj nisu isti kao u CLR, fale neki specijalni simboli!)
  - "KT" (pdf, 44859 kB)
  - Programming Pearls (2. izdanje) — "PP2" (djvu, 2074 kB)
  - Programming Pearls (1. izdanje) — "PP1" (djvu, 1784 kB, ili pdf, 11028 kB)
  - More Programming Pearls — "More_PP" (djvu, 1555 kB, ili pdf, 11291 kB).
  - Dodatni materijali uz Programming Pearls (2. izdanje) — "PP2_add_web" (pdf, 1294 kB).
    Sve stranice (nekadašnjeg) weba s dodatnim materijalima za PP2 (link na to više ne radi).

Čitanje: Sumatra PDF — besplatni program koji čita "pdf" i "djvu" na Windowsima.