Ivan Drecun

Matematički fakultet, Univerzitet u Beogradu
Katedra za računarstvo i informatiku

Algoritmi i strukture podataka


Važne informacije

Studenti grupe 2i1 (kod profesora Živkovića) imaju pravo na polaganje usmenog dela ispita ukoliko su na pismenom delu ostvarili bar 14 poena, ili su u zbiru na pismenom delu i predispitnim obavezama ostvarili bar 25 poena.

Studenti grupe 2i2 (kod profesora Marića) imaju pravo na polaganje usmenog dela ispita ukoliko su na pismenom delu ostvarili bar 14 poena, pri čemu će oni koji su ostvarili tačno 14 poena pored ispitnih pitanja dobiti i zadatak koji treba da reše tokom usmenog dela.

Rezultate ispita u roku januar 2 možete pronaći ovde. Uvid u radove je moguć putem mejla, najkasnije 2. februara.

Rezultate ispita u roku januar 1 možete pronaći ovde.

Konačne rezultate kolokvijuma možete pronaći ovde.

O kursu

Profesori: Filip Marić, Miodrag Živković
Asistenti: Sana Stojanović Đurđević, Ivan Drecun

Obaveze na predmetu:
  • Praktični kolokvijum - 20 poena
  • Teorijski kolokvijum - 10 poena
  • Praktični deo ispita - 30 poena
  • Usmeni deo ispita - 40 poena

Neophodno je ostvariti bar 50% poena na završnom ispitu.

Literatura

Svi primeri obrađeni na vežbama uzeti su iz skripte Algoritmi i strukture podataka Filipa Marića, Vesne Marinković i Mladena Nikolića.

Vežbe

  1. Uvod u C++/STL (kodovi)
  2. Korektnost algoritama
  3. Složenost algoritama (kodovi)
  4. Induktivno-rekurzivna konstrukcija (kodovi)
  5. Strukture podataka (stek, red) (kodovi)
  6. Strukture podataka (red sa prioritetom, skup, mapa) (kodovi)
  7. Implementacija struktura podataka (red, stek, hip) (kodovi)
  8. Implementacija struktura podataka (skup), primena sortiranja (kodovi)
  9. Tehnika dva pokazivača i stabilno sortiranje (par brojeva datog zbira, trojka brojeva sa zbirom nula, segmenti niza prirodnih brojeva koji imaju dati zbir, najkraća podniska koja sadrži sva data slova, sortiranje prebrojavanjem, sortiranje razvrstavanjem, sortiranje višestrukim razvrstavanjem)
  10. Dekompozicija (broj inverzija u nizu, quick-select, maksimalni zbir segmenta, Karacubin algoritam množenja polinoma)
  11. Pretraga (podskupovi, varijacije, binarni zapisi bez uzastopnih jedinica, permutacije, izlazak iz lavirinta)
  12. Dinamičko programiranje i pohlepni algoritmi (Fibonačijevi brojevi, broj particija, najduži zajednički podniz, najduži palindromski podniz, najveći kvadrat u matrici, najveći pokupljen zbir, mentori, vraćanje kusura, raspored sa najmanjim brojem učionica)