Saša Singer:  Oblikovanje i analiza algoritama

• Za pristup datotekama koje sadrže osobne podatke studenata potrebna je autorizacija:
  • degiorgi.math.hr:  "kolegijsko" korisničko ime (login) i lozinka (password) — te podatke dobijete na prvom predavanju!
  • web.math.hr:  vaše AAI@EduHr korisničko ime i lozinka.
  Takve datoteke dostupne su samo do kraja semestra u kojem ide nastava iz kolegija.

Zadnja promjena:  1. ožujka 2020.

• Semestar je gotov — datoteke s osobnim podacima više nisu dostupne.


• Završni rezultati (bodovi/ocjene).


• Rezultati popravnog kolokvija.
  Uvidi: petak, 14.2., u 12 sati (konzultacije, ured 227).


• Zadnji rok za predaju zadaća: petak, 14. veljače 2020., od 12 do 14 sati. Koga nema do 14 sati, zakasnio je!


• Rezultati 2. kolokvija.
  Uvidi, može predavanje zadaća nakon uvida:   petak, 7.2., u 12:15 (konzultacije, ured 227).
      Studenti s barem 45 bodova na kolokvijima ne moraju predati zadaću, ako su zadovoljni ocjenom iz trenutnih bodova.
      Studenti s 30–44 bodova na kolokvijima moraju predati zadaću za prolaznu ocjenu.


• Seminarske teme i organizacija seminara.


• Rezultati 1. kolokvija.   Ispričavam se za kašnjenje.
  Uvidi:   ponedjeljak, 2.12., od 12:15 do 14 sati (ured 227);   utorak, 3.12., u pauzi i iza nastave.
      Diskusija rješenja na nastavi 3.12.


• Domaće zadaće (prošireni popis).


• Nastava: utorak, 14–17 sati u (A001).


• Konzultacije: samo za OAA — utorak, 17 sati (iza predavanja),  petak, 12–14 sati,  ili po dogovoru.


• Termini kolokvija (razred B1):
  • Prvi kolokvij: srijeda, 20. studenog 2019., u 9 sati
  • Drugi kolokvij: srijeda, 29. siječnja 2020., u 9 sati
  • Popravni kolokvij: srijeda, 12. veljače 2020., u 9 sati

• Službena web-stranica kolegija.


• Forum za kolegij.

Materijali i linkovi:

• Zametak buduće skripte (nova literatura)   (pdf, 426 kB, 13.09.2011. u 10:59)
  Trenutno: Prosječna složenost quicksort algoritma, Brza Fourierova transformacija (FFT).


• Osnovni dio predavanja (scan papira za predavanja):
  • Uvod u složenost   (pdf, 4632 kB, 26.02.2005. u 17:28)
  • Brza sumacija alternirajućih redova (članak, dodatak uz 3. predavanje)   (pdf, 96 kB, 10.04.2007. u 13:13)
  • Ocjena sume integralom   (pdf, 164 kB, 18.10.2011. u 23:21)
  • Dokazi nekih tvrdnji iz Prop. 4 u 1. poglavlju (str. 61–62)   (pdf, 106 kB, 04.11.2014. u 10:21)
  • Rekurzivni algoritmi   (pdf, 720 kB, 26.02.2005. u 18:51)
  • Sortiranje   (pdf, 617 kB, 09.05.2005. u 01:18)
  • Quicksort: jednaka vjerojatnost permutacija nakon particije   (pdf, 92 kB, 30.05.2008. u 12:37)
  • Metode za oblikovanje algoritama   (pdf, 1512 kB, 26.02.2005. u 18:27)
  • Dinamičko programiranje   (pdf, 554 kB, 26.02.2005. u 18:42)
  • Brza Fourierova transformacija (sve zajedno)   (pdf, 3811 kB, 04.06.2008. u 20:33)
    • Leptir, paralelni FFT (slike)   (pdf, 69 kB, 10.12.2012. u 10:36)
    • Brzi iterativni FFT   (pdf, 599 kB, 11.12.2012. u 12:27)
    • Kratko ponavljanje FFT   (pdf, 183 kB, 13.12.2011. u 11:28)
    • Brzo množenje polinoma   (pdf, 218 kB, 13.12.2011. u 11:29)
    • FFT za opći n   (pdf, 605 kB, 13.12.2011. u 11:30)
    • FFT u obradi signala (uvod)   (pdf, 72 kB, 13.12.2011. u 11:30)


• Svi kolokviji iz OAA (od akad. god. 2007/08 do 2019/20).   (zip pdf-ova, 1319 kB, 23.02.2020. u 12:15)


• Pedantna rješenja prva dva zadatka s 1. kolokvija (2015/16)   (pdf, 978 kB, 07.12.2015. u 02:36)
• Pedantna rješenja prva dva zadatka s 1. kolokvija (2012/13)   (pdf, 195 kB, 13.11.2014. u 22:17)


• Skica rješenja nekih zadataka s 2. i popravnog kolokvija   (pdf, 5094 kB, 24.01.2018. u 19:33)
• Skica rješenja prva dva zadatka s 2. kolokvija (2015/16)   (pdf, 54 kB, 24.01.2018. u 15:35)
• Pohlepni algoritmi (pedantna argumentacija) magnetska traka - 2. kolokvij (2009/10)   (pdf, 64 kB, 25.01.2018. u 01:25)



---



• Oblikovanje i analiza algoritama (akad. god. 2019/20):
  • Kolokviji: 1. kolokvij,  2. kolokvij,  popravni kolokvij.
  • Seminarske teme.
  • Domaće zadaće.
  • Pravila polaganja i ocjenjivanja   (pdf, 257 kB, 11.08.2018. u 12:04)

  Materijali (prezentacije) za predavanja:

  • 1. predavanje — Uvod u kolegij, pravila ocjenjivanja i kodeks ponašanja, literatura i dodatna literatura   (pdf, 932 kB, 01.10.2019. u 10:58)
  • 3. predavanje — Sumacija reda za ln 2, zbrajanje matrica, priča o cacheu   (pdf, 3124 kB, 14.10.2019. u 21:50)
  • 4. predavanje — Množenje matrica, blokovsko množenje matrica   (pdf, 1224 kB, 14.10.2019. u 21:52)
  • 5. predavanje — Hanojski tornjevi   (pdf, 1358 kB, 24.10.2019. u 22:34)
  • 9. predavanje — Fibonaccijevi brojevi, brzo računanje n-tog člana rekurzije  [nepotpuno]   (pdf, 874 kB, 10.12.2019. u 22:18)
  
  

---



• Stari materijali (iz akad. god. 2018/19 i ranijih godina) prebačeni su ovdje.

Dodatni materijali i linkovi:

• Sve prezentacije seminara iz ranijih godina (objavljeno uz dozvolu autora).
• Sve seminarske teme iz ranijih godina.
• Sve domaće zadaće iz ranijih godina.


• Herbert S. Wilf, ``Algorithms and Complexity'', Internet Edition, Summer, 1994.


• David M. Mount, `` Design and Analysis of Computer Algorithms'', CMSC 451, University of Maryland, 2015.
      Osobna stranica autora, na kojoj ima još interesantnih stvari (pod Teaching).


• Steven Skiena, osobna stranica, na kojoj ima još interesantnih stvari (pod Courses, Books, Teaching). Na primjer,
  • CSE 373, Analysis of Algorithms, Stony Brook University, Fall 2019
  • CSE 392, Programming Challenges, Stony Brook University, Spring 2012
  • ``The Algorithm Design Manual, 2nd Edition'', stranica za knjigu s popratnim materijalima
  Nažalost, stranica za knjigu ``Programming Challenges'' ne radi.


• Robert Sedgewick, Kevin Wayne, `` Algorithms, 4th Edition'', stranice s materijalima uz knjigu.

Kursevi iz Oblikovanja i analize algoritama s javno dostupnim materijalima:

• University of Maryland (SAD):
  • CMSC 451: Design and Analysis of Computer Algorithms (Fall 2017) (instructor David Mount).
        Ima gomila materijala - pogledati linkove lijevo, pod "Lectures" i "Handouts".


• Stony Brook University (SAD):
  • CSE 373, Analysis of Algorithms (Fall 2019) (instructor Steven S. Skiena).
        Ima svega - posebno, pogledati pod "Lectures Notes" i "Homework Assignments".


• Massachusetts Institute of Technology = MIT (SAD):
  • 6.046J / 18.410J: Design and Analysis of Algorithms (MIT Open CourseWare).


• Stanford University (SAD):
  • CS 161: Design and Analysis of Algorithms (Fall 2018) (instructor Aviad Rubinstein).
        Upravo ide, materijali se dodaju. Predavanja i vježbe ("Sections", bez rješenja) su dostupni. Ispiti, zadaće i rješenja nisu dostupni.
  • CS 161: Design and Analysis of Algorithms (Fall 2017) (instructor Mary Wootters).
        Prekrasan web s gomilom materijala (pogledati linkove lijevo). Rješenja su dostupna samo za vježbe ("Sections").
  • CS 161: Design and Analysis of Algorithms (Spring 2017) (instructor Mary Wootters).
        Ima gomilu materijala: predavanja, vježbe (bez rješenja), zadaće (bez rješenja). Ispiti i rješenja više nisu dostupni.
  • CS 161: Design and Analysis of Algorithms (Fall 2016) (instructor Moses Charikar).
        Ima gomilu materijala: predavanja, vježbe (bez rješenja), zadaće (bez rješenja). Ispiti i rješenja više nisu dostupni.
  • CS 161: Design and Analysis of Algorithms (Summer 2016) (instructor Jessica Su).
        Ima gomilu materijala: predavanja, vježbe, zadaće (bez rješenja). Rješenja više nisu dostupna.
  • CS 161: Design and Analysis of Algorithms (Spring 2016) (instructor Virginia Vassilevska Williams).
        Ima gomilu materijala: predavanja (isplati se pogledati), ispiti, zadaće. Rješenja su još uvijek dostupna.


• University of California at Berkeley (SAD):
  • CS 170: Efficient Algorithms and Intractable Problems (Fall 2018) (instructors Alessandro Chiesa, Satish Rao).
        Upravo ide, materijali se dodaju. Knjiga (textbook) je ista kao prošle dvije godine (potražite po webu).
  • CS 170: Efficient Algorithms and Intractable Problems (Fall 2017) (instructors Prasad Raghavendra, Sanjam Garg).
        Ima zadataka, rješenja, domaćih zadaća i ispita. Knjiga (textbook) je ista kao 2016. godine (potražite po webu).
  • CS 170: Efficient Algorithms and Intractable Problems (Fall 2016) (instructors Christos H. Papadimitriou, Luca Trevisan).
        Nema baš puno materijala, ali kliknite na knjigu (na vrhu) i onda malo tražite po webu.

Napomene:
• Svi materijali dostupni na ovim stranicama zaštićeni su Zakonom o autorskom pravu.
• Prema tome, bez dozvole autora, nije ih dozvoljeno distribuirati i umnožavati.
• Svakom pojedincu dozvoljeno ih je koristiti samo za osobne potrebe.