Циљ и исход предмета
Упознавање са логичком организацијом и меморијском репрезентацијом линеарних и нелинеарних структура података, основним операцијама и типичним применама ових структура. Студенти су оспособљени за програмску имплементацију линеарних и нелинеарних структура података, као и алгоритама за рад са њима у типичним применама, као што су претраживање и сортирање.
Теоријска настава
Линеарне структуре. Низови. Листе. Стекови. Редови чекања. Нелинеарне структуре. Стабла: бинарна стабла, обилазак стабла, минимизација дужине пута. Графови. Начини представљања, обилазак графа по ширини и по дубини, одређивање артикулационих тачака повезаног графа, одређивање мостова графа, издвајање двоструко повезаних компоненти, издвајање компоненти јаке повезаности. одређивање тополошког поретка и критичног пута, повезујућа стабла и минимална повезујућа стабла, одређивање достижности и најкраћих растојања. Претраживање. Основни метод и побољшања. Стабло бинарног претраживања, AVL стабла, оптимално стабло. Стабло м-арног претраживања. B, B* i B+ стабла, стабла дигиталног претраживања. Хеширање. Хеш функције, разрешавање колизија, спољашње хеширање. Сортирање. Сортирање поређењем – методи уметања, селекције, замене, методи линеарне сложености. Алгоритми сортирања временске сложености O(N log N). Доња граница сложености сортирања.
Практична настава
Имплементација неких од структура које су приказане на предавањима: повезане листе, стек, ред, бинарно стабло, приоритетни ред, бинарно претраживачко стабло, AVL стабло, B стабло, хеш табеле. Имплементација алгоритама за сортирање. Дизајн и анализа алгоритама за разне алгоритамске проблеме уз примену структура података и алгоритама који су приказани на предавањима (при анализи посебан акценат ставити на процени најмање повољног случаја, као и просечног случаја).