Saša Singer: Oblikovanje i analiza algoritama

Saša Singer: Oblikovanje i analiza algoritama

(4.3.2018.) 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.
(24.5.2018.) Prema uputi o primjeni Opće uredbe o zaštiti podataka (tzv. GDPR), dostupne su samo "aktualne" datoteke tog tipa.

Zadnja promjena: 11. prosinca 2018.

Novo: 9. predavanje — Fibonaccijevi brojevi (algoritmi i rezultati) [nepotpuno]

Rezultati 1. kolokvija. Ispričavam se za kašnjenje.
Uvidi: petak, 30.11., u 12:15 (konzultacije, ured 227); utorak, 4.12., u pauzi i iza nastave.
Diskusija rješenja na nastavi 4.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, 21. studenog 2018., u 9 sati
- Drugi kolokvij: srijeda, 30. siječnja 2019., u 9 sati
- Popravni kolokvij: srijeda, 13. veljače 2019., u 9 sati

Službena web-stranica kolegija.

Forum za kolegij.

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 2017/18). (zip pdf-ova, 997 kB, 15.02.2018. u 18:29)

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. 2018/19):
- Rezultati 1. kolokvija.
- 1. kolokvij.
- 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, 914 kB, 03.10.2018. u 15:57)
- 3. predavanje — Sumacija reda za ln 2, zbrajanje matrica, priča o cacheu (pdf, 3124 kB, 15.10.2018. u 22:26)
- 4. predavanje — Množenje matrica, blokovsko množenje matrica (pdf, 1224 kB, 15.10.2018. u 22:27)
- 5. predavanje — Hanojski tornjevi (pdf, 1248 kB, 29.10.2018. u 23:03)
- 9. predavanje — Fibonaccijevi brojevi (algoritmi i rezultati) [nepotpuno] (pdf, 511 kB, 11.12.2018. u 12:13)

Oblikovanje i analiza algoritama (akad. god. 2017/18):
- Kolokviji: 1. kolokvij, 2. kolokvij, popravni kolokvij.
- Prezentacije održanih seminara.
- Seminarske teme.
- Domaće zadaće.
- Pravila polaganja i ocjenjivanja (pdf, 55 kB, 25.08.2015. u 21:19)
Materijali (prezentacije) za predavanja:
- 1. predavanje — Uvod u kolegij, pravila ocjenjivanja i kodeks ponašanja, literatura i dodatna literatura (pdf, 913 kB, 12.10.2017. u 22:28)
- 3. predavanje — Sumacija reda za ln 2, zbrajanje matrica, priča o cacheu (pdf, 3144 kB, 16.10.2017. u 15:09)
- 4. predavanje — Množenje matrica, blokovsko množenje matrica (pdf, 1243 kB, 16.10.2017. u 15:18)
- 5. predavanje — Hanojski tornjevi (pdf, 1240 kB, 31.10.2017. u 11:43)

Stari materijali (iz akad. god. 2016/17 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 2017
- 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.

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".

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.