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 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.
course aims in English
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.
learning outcomes in the course in Est.
- 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, tunneb koodistiili ja dokumenteerimise põhitõdesid.
learning outcomes in the course in Eng.
- 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.
brief description of the course in Estonian
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.
brief description of the course in English
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.
type of assessment in Estonian
eksam
type of assessment in English
examination
Threshold: Test result > 50%
Threshold: Summary result from all homeworks >50% and individual programming task (written report compulsory) passed.
independent study in Estonian
-
independent study in English
-
study literature
Michael T. Goodrich, Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley and Sons.
Course homepage: http://enos.itcollege.ee/%7ejpoial/algorithms/
study forms and load
daytime study: weekly hours
3.0
session-based study work load (in a semester):