Objectives and outcomes
Introduction to the logical organization and memory representation of linear and nonlinear data
structures, basic operations and typical applications of these structures. Students are trained to
implement linear and nonlinear data structures, as well as algorithms in typical applications such as
searching and sorting.
Lectures
Linear structures. Arrays. List. Stacks. Queues. Nonlinear structures. Trees: binary trees, tree tour, path
length minimization. Graphs. Representation, Depth first search and Breadth first search, determining
articulation points of a connected graph, determination of graph bridges, separation of doubly connected
components, separation of components of strong connectivity. Determination of topological order and
critical path, spanning trees and minimum spanning trees, determination of shortest distances.
Searching. Basic method and improvements. Binary search tree, AVL tree, optimal tree. M-ary search
tree. B, B* and B+ trees, digital search trees. Hashing. Hash functions, collision resolution, external
hashing. Sorting. Sort by comparison – methods of insertion, selection, substitution, methods of linear
complexity. Time complexity sorting algorithms O (N log N). Lower limit of sorting complexity.
Practical classes
Implementation of some structures presented in the lectures: linked lists, stack, queue, binary tree,
priority queue, binary search tree, AVL tree, B tree, hash tables. Implementation of sorting algorithms.
Design and analysis of algorithms for various algorithmic problems with the application of data structures
and algorithms presented in lectures (during the analysis, special emphasis should be places on the
estimation of the worst case, as well as on the average case).