IT - Data Structures and Algorithms

Strategije programiranja. Rekurzija. Osnove složenosti algoritama. Pretraživanje: sekvencijalno, binarno, stabla. Sortiranje: bubble, selection, insertion, shell, quick, heap. Strukture podataka: niz, vezana lista, stablo, hash tablica. Uređeni i neuređeni kontejneri: stog, red, lista skup, mapa, prioritetni red, graf. Dinamički algoritmi: Fibonnacijev niz, optimalno binarno stablo, množenje niza matrica. Grafovi: minimalno stablo, Dijkstrov algoritam. Rješavanje težih problema: "Problem trgovačkog putnika", "Problem kineskog poštara".

Kolegij pruža temeljna znanja o uporabi i svojstvima često korištenih struktura podataka, o izvedbi poznatijih algoritama, analizi vremena izvedbe i efikasnosti algoritama, te implementaciji zadanih algoritama.

1. Understanding and knowing how to describe the meaning of algorithm complexity. Finding complexity of more difficult algorithms.
2. Understand the concept of abstract data type and its application in software development. Understand the basic data structure. Understand the methods of implementation of abstract data types with the use of data structure.
3. Knowing basic ATP's and differences in their behavior, way of application and performances in various scenarios.
4. Understanding algorithms' processes during the course, being able to describe algorithms, but also the course of executing those algorithms in concrete data.
5. Being able to choose and use algorithms, data structure and abstract data types independently, in given conditions and regarding the practical requirements of the developing software.

Kolegij pruža specijalistička znanja s područja programiranja kao nadogradnju jezgre računarstva, te obučava polaznika za efikasnu uporabu složenih struktura podataka i algoritama obrade

1. Cormen, Thomas H: "Introduction to Algorithms", 2nd edition, McGraw-Hill, New York 2001.
2. Knuth, Donald E: "The Art of Computer Programming, Vol. 1, 3" Addison-Wesley, 1997

1. Aho, Alfred V; Hopcroft, John E: "Data structures and algorithms", Addison-Wesley, Massachusetts 1983.
2. Manber, Udi: Introduction To Algorithms - A Creative Approach, Addison-Wesley, 1989.

1. 1. Uvod i motivacija za kolegij 2. Rekurzija 3. Standardne funkcije za pretraživanje i sortiranje (bsearch, qsort)
2. 1. Definicija algoritma, zahtjevi za algoritam, analiza algoritma 2. O-notacija, gornja i donja ograda 3. Mjerenje složenosti (zadaća, ulaz)
3. 1. Sortiranje (uvod) 2. Sortiranje izmjenjivanjem (Bubble) 3. Sortiranje odabiranjem (Selection) 4. Sortiranje ubacivanjem (Insertion i Shell) 5. Sortiranje izmjenjivanjem (Quick) 6. Usporedba algoritama sortiranja i zaključak
4. 1. Dugi integeri (definicija, zbrajanje, oduzimanje, množenje) 2. Divide and conquer princip 3. Divide and conquer primjeri 3.1. min/max 3.2. k-ti element 3.3. Karatsubino množenje 4. Divide and conquer (složenost, zaključak) 5. Dinamičko programiranje (definicija, top/down, bottom/up) 5.1. 0-1 Knapsack 5.2. Chain multiplication 6. Backtracking
5. 1. Struktura vezane liste 2. Apstraktni tip podataka 3. Sučelje 4. ATP u C-u 5. ATP Stog 5.1. Sučelje 5.2. Implementacije (niz, vezana lista) 6. ATP Red 6.1. Sučelje 6.2. Implementacije (niz, vezana lista)
6. 1. Iteratori 2. ATP Lista 2.1. Sučelje 2.2. Implementacije (niz, vezana lista)
7. 1. ATP Set 1.1. Sučelje 1.2. Implementacije (niz, sortirana vezana lista, bit-vektor, hash tablica)
8. PRVI KOLOKVIJ
9. 1. Stabla 1.1. Definicije 1.2. Reprezentacija 1.3. Obilasci 2. Binarna stabla pretraživanja 2.1. Algoritmi 2.2. Složenost
10. 1. Hash tablica 1.1. Vrste 1.2. Obrade sudara 1.3. Re-hashing 2. ATP Map 2.1. Sučelje 2.2. Implementacije (stablo, hash tablica)
11. 1. Struktura hrpe (heap) 2. ATP Prioritetni red 2.1. Sučelje 2.2. Implementacije (hrpa)
12. 1. Grafovi 1.1. Definicije 1.2. Primjene 1.3. Nastanak teorije grafova 1.4. Reprezentacija
13. 1. ATP Graph 2. Grafovi (nastavak) 2.1. Obilasci 2.1.1. DFS 2.1.2. BFS 2.2. Minimalna razapinjuća stabla (MST) 2.2.1. Kruskalov algoritam 2.2.2. Primov algoritam 2.2.3. Složenost
14. 1. Grafovi (nastavak) 1.1. Najkraći put (Dijkstrin algoritam) 1.2. Kratki pregled nekih problema u teoriji grafova
15. DRUGI KOLOKVIJ

1. 1. Ponavljanje: strukture, datoteke, predprocesor, stringovi, dinamička alokacija memorije.
2. 1. Određivanje vremenske i prostorne složenosti poznatih algoritama: izbacivanje člana iz niza, strlen, strcmp, strcat. 2. Rekurzivne implementacije poznatih algoritama: faktorijeli, strlen, Fibonaccievi brojevi.
3. 1. Demonstracija algoritama sortiranja: 1.1 Bubble 1.2 Selection 1.3 Insertion 1.4 Shell 1.5 Quick
4. 1. Knapscak. 2. Ponavljanje rekurzije i priprema za implementaciju rekurzivnog spusta na laboratorijskim vježbama.
5. 1. Operacije nad vezanom listom. 2. Implementacija ATP Stoga i ATP Reda nizom 3. Uvod u implementaciju ATP Stoga i ATP Reda vezanom listom (priprema za laboratorijske vježbe)
6. 1. Implementacija ATP Liste nizom. 2. Implementacija ATP Liste vezanom listom.
7. 1. Implementacija ATP Skupa nizom. 2. Implementacija ATP Skupa vezanom listom.
8. 1. Rješavanje zadataka sa prvog kolokvija.
9. 1. Operacije nad stablima: 1.1 Obilasci. 1.2 Dodavanje čvorova. 1.3 Brisanje čvorova.
10. 1. Rješavanje zadataka upotrebom ATP Mape.
11. 1. Rješavanje zadataka upotrebom ATP Prioritetnog reda.
12. 1. Najkraći put (Dijkstrin algoritam) 2. Detektiranje ciklusa u grafu.
13. 1. Minimalna razapinjuća stabla (MST)
14. 1. Kratki pregled nekih problema u teoriji grafova
15. 1. Rješavanje zadataka sa drugog kolokvija.

1. Priprema, korištenje Visual Studia za projekte sa više datoteka. Utvrđivanje elemenata C-jezika potrebnih za sljedeće vježbe (strukture, pokazivači).
2. Iterativne i rekurzivna implementacija binarne pretrage.
3. Mjerenje vremena izvršavanja pripremljenih algoritama sortiranja. Hibridno sortiranje.
4. Rekurzivni spust kroz matricu.
5. Rekurzivni spust kroz matricu (backtracking optimizacije, pamćenje puta).
6. Implementacije ATP Stoga i ATP Reda vezanom listom
7. Not defined
8. Not defined

1. Tijekom semestra održat će se dva međuispita (kolokvija) – kombinirano teorije i zadataka u 8. i 14. tjednu nastave. Na završnom ispitu studenti koji polože međuispite oslobođeni su polaganja ispita. Ukoliko student položi samo jedan od kolokvija, tijekom ljetnih ispitnih rokova umjesto završnog ispita omogućeno mu je polaganje gradiva međuispita koji nije položio. Kolokvij je zadan pismeno, u obliku 5 zadataka. Rješavanje kolokvija traje 90 minuta, nije dopušteno korištenje materijala ispita ni drugih pomagala. Sadržaj prvog kolokvija: Složenost algoritama, Algoritmi za sortiranje (opis i provedba na konkretnim podacima) Dinamičko programiranje ATP Stack, Queue, List Vezane liste (fragmenti koda)
2. Sadržaj drugog kolokvija: ATP Set, Dictionary, Map, Prioritetni red Hash tablica Stabla, Binarna stabla pretraživanja (opis i provedba na podacima) Hrpa (opis i provedba na podacima) Algoritmi na grafovima

1. Završni ispit zadaje se u obliku 7-10 pismenih zadataka iz teorije i izvedbe algoritama. Rješavanje ispita traje 90 minuta. Dopušteno je korištenje isključivo tablice ATP operacija dostupne na strnici predmeta. Po potrebi predavač može zatražiti usmeno odgovaranje. Uvjet za konačnu pozitivnu ocjenu je odrada svih laboratorijskih vježbi, prisustvo na barem 50% predavanja, pozitivna ocjena međuispita ili završnog ispita, uz eventualnu korekciju po usmenom odgovoru. Ocjena (%) = (K1 + K2) / 2 ili Ocjena (%) = ZI (u slučaju da student nije položio oba međuispita do kraja ljetnih ispitnih rokova tekuće nastavne godine) K1, K2 – bodovi iz kombiniranih međuispita. ZI – bodovi iz završnog ispita Konačna se ocjena utvrđuje na sljedeći način: [0, 40] 1 [40, 55) 2 [55, 70) 3 [70, 85) 4 [85, 100] 5 Sadržaj ispita: Složenost algoritama, Algoritmi za sortiranje (opis i provedba na konkretnim podacima), Dinamičko programiranje, Vezane liste, ATP Stog, Red, Lista, Skup, Stabla, Binarna stabla pretraživanja (opis i provedba na podacima) Hash tablica ATP Mapa, Prioritetni red Hrpa (opis i provedba na podacima) Grafovi

1. 1. Konzultacije 2. Analiza ponuđenih implementacija algoritama. 3. Samostalno rješavanje zadataka 4. Rad u laboratoriju