course aims in Estonian
Aine rolliks õppekavas on süvendada algoritmilise mõtlemise, analüüsi ning praktilise programmeerimise vilumust. Õppeaine eesmärgiks on anda õppurile ülevaade andmestruktuuridest ning nende realiseerimisest, samuti tutvustada olulisemaid meetodeid klassikaliste algoritmikaprobleemide lahendamisel, s.h. otsimine ja järjestamine; andmete organiseerimine: pinu, järjekord, ahel, paisktabel, puu, kuhi, graaf; rekursioon, ammendav otsing, dünaamiline kavandamine jt. programmeerimistehnikad.
course aims in English
Role of the course in curricula is to develop student's algorithmic thinking through analysis of algorithms and data structures, also deepen her programming skills.
The course provides an overview of data structures, also guidelines to their analysis and implementation. Classical data structures are presented: linked list, stack, queue, priority queue, dequeue, hash table, tree, binary tree, heap, graph, etc. Course covers techniques for solving common algorithmic problems – searching, sorting, data organization, using recursion, backtracking, dynamic programming, exhaustive search, etc.
learning outcomes in the course in Est.
Aine läbinu:
1. Tunneb põhilisi andmestruktuure (ahel, pinu, järjekord, kahepoolne järjekord, paisktabel, puu, kahendpuu, kuhi, graaf), nende omadusi ning nendega seotud algoritme ja tehnikaid (andmestruktuuride läbimine, teede leidmine, otsimine ja järjestamine, "ahned" algoritmid, rekursioon, dünaamiline kavandamine, ammendav otsing jt. ). Hindamismeetod: kirjalik eksam.
2. Oskab andmestruktuure kasutada praktiliste programmeerimisülesannete lahendamiseks. Hindamismeetod: praktikumid.
3. Oskab dünaamilisi andmestruktuure kavandada ning realiseerida. Hindamismeetod: individuaalne projektitöö
learning outcomes in the course in Eng.
1. Student is familiar with basic data structures (linked list, stack, queue, dequeue, hash table, tree, binary tree, heap, graph), knows their properties, appropriate terminology and algorithms or techniques related to these structures (traversal methods, path finding, searching, sorting, “greedy” algorithms, recursion, dynamic programming, backtracking, etc.). Assessment method - written exam.
2. Student can use data structures in practical programming tasks. Assessment method - practices.
3. Student is able to design and implement a dynamic data structure. Assessment method - individual project work.
brief description of the course in Estonian
Keerukuse hindamise vahendid, levinumate keerukusklasside iseloomustus.
Otsimine: lineaarne otsimine, kahendotsimine, paisktabel.
Järjestamine: pistemeetod, mullimeetod, valikumeetod, kahendpistemeetod, kiirmeetod, ühildamismeetod, loendamismeetod, positsioonimeetod, kimbumeetod.
Abstraktse andmetüübi mõiste. Dünaamilised ja staatilised andmestruktuurid. Pinu, järjekord, eelistusjärjekord, kahepoolne järjekord. Ahel, ringahel, topeltseotud ahel. Pööratud poola kuju.
Puustruktuurid. Puude töötlemise tüüpilised algoritmid - preorder, postorder, inorder. Puu esitusvõimalused.
Graaf ja sellega seotud mõisted. Orienteeritud ja orienteerimata graaf, multigraaf. Graafi kujutamisviisid, külgnevusmaatriks, lühimate teepikkuste maatriks. Graafi töötlemine sügavuti ja laiuti. Näitealgoritmid graafidel.
Kahendotsimise puu, AVL-puu, värvitud puu, B-puu. Kahendkuhi, kuhjameetod.
Kodeerimine ja pakkimine. Huffmani ja Shannon-Fano meetodid.
Programmeerimistehnikad: rekursioon, ammendav otsing, dünaamiline kavandamine.
Projektitööna peab iga üliõpilane iseseisvalt kavandama ning realiseerima mingi dünaamilise andmestruktuuri.
brief description of the course in English
Basics tools of analysis of algorithms, properties of common complexity classes.
Searching: linear search, binary search, hashtable.
Sorting: insertion sort, bubble sort, selection sort, binary insertion sort, quicksort, merge sort, counting sort, radix sort, bucket sort.
Abstract data types. Dynamic and static data structures. Stack, queue, priority queue and dequeue. Linked list, circular list, doubly linked list. Reverse Polish notation (RPN).
Tree structures. Traversal of trees – pre-order, post-order, in-order. Forms of expression for trees.
Basics of graphs. Directed and undirected graphs, multigraphs. Representation of graphs, adjacency matrix, matrix of shortest pathlengths. Depth-first and breadth-first traversal of a graph. Examples of algorithms on graphs.
Binary search trees, AVL trees, red-black trees, B-trees. Heaps, heapsort.
Coding and compressing, coding schemes: Huffman, Shannon-Fano.
Students have to write an individual project on design and implementation of a dynamic data structure.
type of assessment in Estonian
Andmestruktuuride projekt - 30%, harjutused - 30%, kirjalik eksam - 40%
type of assessment in English
Data structures project - 30%, exercises - 30%, written exam - 40%
independent study in Estonian
-
independent study in English
-
study literature
https://en.wikibooks.org/wiki/Data_Structures
https://www.teaduskool.ut.ee/sites/default/files/teaduskool/oppetoo/voistlusprogrammeerimine_i_osa.pdf
Course homepage: http//enos.itcollege.ee/~jpoial/andmestruktuurid/
study forms and load
daytime study: weekly hours
3.0
session-based study work load (in a semester):