Course description - Course content

Course description:

The course focuses on the study of basic data structures, i.e. arrays, stacks, queues, lists, trees, etc., as well as on more complex data structures such as balanced trees, graphs and others. In addition, the technique of hashing will be taught, as well as data structures for the implementation of dynamic dictionaries, simple sets and sets with special operations. Selected topics on sorting and basic techniques of algorithm design will be also taught.

Course content:

- Introduction: Basic concepts on algorithms and data structures, Proof techniques (proof by example or counterexample, proof by contradiction, mathematical induction), RAM model, Analysis of algorithms, Time complexity , Asymptotic analysis (in terms of Ο, Ω, Θ), Standard complexity classes, Mathematical background , Recursive algorithms and their analysis, Recursive relations, Experimental analysis.
- Arrays: Operations on Arrays, Multi-dimensional Arrays, Symmetric and Triangular Arrays, Sparse Arrays.
- Basic data structures: Stacks (abstract data type, static and dynamic implementations, static implementation of multiple stacks, applications, complexity), stacks that support the multipop() operation, Amortized analysis. Queues (abstract data type, static and dynamic implementation, complezity, applications). Lists (unsorted and sorted lists, guard node, list traversals, zig-zag traversals, doubly linked lists, complexity, applications).
- Trees: Definition, types of trees and their properties, implementation, tree traversals, ordered trees.
- Sets & Dictionaries: Abstract data type, Implementation using linked lists, Move-to-front and Transpose heuristic, Binary search, Expected analysis, Binary Search Trees.
- Balanced Trees: AVL Trees, (2,3)-trees, Red-Black trees.
- Hashing: Chain hashing (separate and coalesced chaining), Open addressing strategies (linear probing, double hashing), Analysis of different strategies, Ordered hashing, Extendible hashing, Hash Functions, Universal Hashing.
- Priority queues: Abstract data type, Implementation using balanced binary search trees, Partially ordered trees, Implementation using Heaps.
- Sorting: InsertionSort, SelectionSort, MergeSort, HeapSort, QuickSort.
- Sets with special operations: Disjoint sets that support Union-find, Up-Trees.
- Graphs: Representation, implementation, traversal, applications.

Keywords: data structures, stacks, lists, queues, sorting, trees.