Aine rolliks õppekavas on süvendada algoritmilise mõtlemise, analüüsi ning praktilise programmeerimise vilumust.
Õppeaine eesmärgiks on anda õppurile ülevaade algoritmidest ja andmestruktuuridest ning nende realiseerimisest keele Java baasil, samuti tutvustada olulisemaid meetodeid klassikaliste algoritmikaprobleemide lahendamisel, s.h. otsimine ja järjestamine; andmete organiseerimine: pinu, järjekord, ahel, paisktabel, puu, kuhi, graaf; sõnetöötluse algoritmid; rekursioon, ammendav otsing, dünaamiline kavandamine jt. programmeerimistehnikad.

Role of the course in curricula is to develop algorithmic thinking and programming skills of students, also to deepen their understanding of methods to analyse and solve algorithmic problems.

This course provides an introduction to algorithms and data structures, also their analysis and implementation in Java programming language. It covers techniques for solving common algorithmic problems – searching, sorting, data organization, using recursion, backtracking, dynamic programming, exhaustive search, text algorithms, etc. Classical data structures are presented: linked list, stack, queue, hash table, tree, binary tree, heap, graph, etc.

Kursuse lõpetanu tunneb põhilisi andmestruktuure (pinu, järjekord, puu, graaf, paisktabel, jt.), nende omadusi ning nendega seotud algoritme ja tehnikaid (rekursioon, otsimine, järjestamine, andmestruktuuride läbimine, teede leidmine, dünaamiline kavandamine jt. ). Üliõpilane oskab hinnata algoritmide ajalist ja mahulist keerukust.
Üliõpilane tunneb programmeerimiskeelt Java ning sellega seotud töövahendeid ulatuses, mis lubab andmestruktuure ja algoritme efektiivselt realiseerida. Ta on võimeline koostama ja analüüsima algoritme ülesannete lahendamiseks kursusel käsitletud teemade piires. Üliõpilane oskab vormistada tehnilist aruannet oma individuaalülesande teemal, suudab töötada koos teiste programmeerijatega, tunneb koodistiili ja dokumenteerimise põhitõdesid ning on valmis end täiendama.

Student is familiar with basic data structures (linked list, stack, queue, 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.). Student is familiar with basic classical algorithms covered in lectures. Student is able to analyse and estimate the time and space complexity of algorithms.
Student knows the Java programming language and appropriate development tools on the level that allows implementing algorithms and data structures efficiently. Student is able to develop and analyse algorithms for solving problems covered in the course. Student can write a technical report about her individual programming task, knows the coding conventions and principles of documentation.

Algoritmi mõiste, algoritmi omadused. Ajaline ja mahuline keerukus. Funktsioonide asümptootiline hindamine, algoritmianalüüs. Levinumad keerukusklassid.
Otsimine ja järjestamine. Lineaarne otsimine, kahendotsimine, paisktabel. Pistemeetod, kahendpistemeetod, mullimeetod, valikumeetod. Kiirmeetod, ühildamismeetod. Loendamismeetod, positsioonimeetod, kimbumeetod. Järjestamismeetodite võrdlus.
Abstraktsed andmetüübid. Pinu ja järjekord, eelistusjärjekord. Pööratud poola kuju. Ahel, ringahel, topeltseotud ahel. Viidastruktuurid.
Puu. Aritmeetilise avaldise puu. Puu läbimise meetodid (eesjärjestus, lõppjärjestus, keskjärjestus). Puu kujutamisviisid tekstina ja viidastruktuurina. Näited.
Graaf. Suunatud ja suunamata graaf. Multigraaf. Teed ja tsüklid. Lihtgraaf, atsükliline graaf. Tugev ja nõrk sidusus, sidususkomponendid. Maatriksesitused (külgnevusmaatriks ja lühimate teepikkuste maatriks). Graafide korrutamine, liitmine ja sulundid. Graafi kujutusviisid. Algoritmid graafidel: Floyd-Warshalli algoritm, topoloogiline järjestamine, Dijkstra algoritm. Graafi läbimine sügavuti ja laiuti. Sidususkomponentide leidmine, minimaalse toese leidmine.
Rekursioon: Hanoi torn, rekursiooni eemaldamine, sabarekursioon. Ammendav otsing: 8 lipu ülesanne, seljakotiülesanne, harude ja tõkete meetod.
Kahendotsimise puu, AVL puu, värvitud puu. B-puu, binomiaalpuu. Kahendkuhi, kuhjameetod.
Sõnealgoritmid: Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp.
Kodeerimine ja pakkimine. Huffmani ja Shannon-Fano meetodid. Ahned algoritmid.
Dünaamiline kavandamine, pikima ühise osasõne leidmine.
Algoritmide korrektsus: eel- ja järeltingimused, tsükliinvariandid. Nõrgima eeltingimuse meetod (Hoare'i meetod). Osaline ja täielik korrektsus, peatuvuse probleem.

Algorithms, properties of algorithms, time complexity and space complexity, asymptotic behaviour of functions, analysis of algorithms, complexity classes.
Searching and sorting. Linear search, binary search, hashing. Insertion sort, binary insertion sort, quicksort, merge sort, counting sort, radix sort, bucket sort. Complexity of different methods.
Abstract data types. Stacks and queues. Reverse Polish notation (RPN). Linked lists and other pointer structures.
Trees. Examples of trees - arithmetic expression tree. Traversal of trees – pre-order, post-order, in-order. Forms of expression for trees - parenthetic expressions, pointer structures, textual representation. Examples of "top-down" and "bottom-up" traversal.
Graphs. Directed and undirected graphs, multigraphs. Cyclic and acyclic graphs. Connected components. Strongly connected and weakly connected graphs. Paths and cycles. Simple graphs. Matrices related to graphs: adjacency matrix, matrix of shortest pathlengths. Operations on graphs: sum, multiplication, transitive closure. Representation and implementation of graphs. Algorithms on graphs: Floyd-Warshall (lengths of shortest paths), topological sort of vertices, depth-first and breadth-first traversal, Dijkstra (shortest path), finding connected components, minimal spanning tree.
Recursion: Hanoi towers, elimination of recursion, tail recursion. Exhaustive search: 8 queens problem, knapsack problem, branch and bound method.
Binary search trees, AVL trees, red-black trees, binomial trees. B-trees. Heaps, heapsort.
String algorithms: exact matching (linear, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp).
Coding and compressing, coding schemes: Huffman, Shannon-Fano. Greedy algoritms: Huffman encoding.
Dynamic programming: longest common subsequence problem.
Correctness of algorithms: preconditions, postconditions, loop invariants, weakest precondition, structural rules, total correctness and partial correctness, halting problem.

-

-

-

-

Kohustuslik kirjandus (K)
Jüri Kiho. Algoritmid ja andmestruktuurid. Tartu Ülikool, 2003.
Täiendav kirjandus (T)
Michael T. Goodrich, Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley and Sons, Inc.

Kursuse koduleht: http://enos.itcollege.ee/%7ejpoial/algoritmid/

-