Data Structures I

I am teaching English version of the course Data Structures 1 [NTIN066] in the summer semester of 2022/2023.

Lectures are held every Tuesday from 14:00 in S3. Sign up for tutorials in SIS.

Please read the complete rules of the game.

date topics sources video
14. 2. Introduction: what is a data structure – interface vs. implementation, static vs. dynamic, the RAM model of computation. Examples of interfaces: queue, set, ordered set, dictionary. Flexible arrays with stretching. [L01] video
21. 2. Different approaches to amortized analysis: aggregation, accounting, coins, potentials. Examples: flexible arrays with stretching and shrinking, binary counters, deletion using tombstones, lazily balanced BB[α] trees. [L01] 2021 video
28. 2. Splay trees: amortized analysis of the Splay operation. Incorporating splaying in Find, Insert, and Delete. [L02] [ST] video
7. 3. Splay trees: remarks on static and dynamic optimality, working set bound. (a,b)-trees: definition, logarithmic height, Find, Insert, Delete, choice of parameters. [L02] [L03] video
14. 3. (a,b)-trees: Amortized bounds for (a,2a-1) and (a,2a)-trees. Top-down splitting and joining. Memory hierarchy: theoretical models – I/O, cache-aware, cache-oblivious. Examples: cache effects on a real machine. [L03] [L05] [CO] video
21. 3. Cache-oblivious algorithms: Sequential scanning of arrays. Sorting: MergeSort, multi-way MergeSort, a remark on FunnelSort and lower bounds. Matrix transposition: cache-aware tiling, cache-oblivious divide & conquer algorithm. [L05] [CO] video
28. 3. Cache-oblivious model versus reality: Sleator-Tarjan theorem on competitivity of LRU. Hashing: buckets with lists (chaining). Choice of hash functions: c-universal systems of functions, expected bucket size, time complexity of hashing with chains, k-independence. [L05] [CO] [STb] [L06] video
4. 4. Hash function families: constructions of universal/independent systems from linear functions. Generic bounds for composition of families, k-independent hashing from polynomials, tabulation hashing. [L06] [Tb] [E10] video
11. 4. Hash tables: open addressing, analysis of linear probing. [L06] [T] video
18. 4. There will be no lecture.
25. 4. Hashing of vectors and strings: scalar products, polynomials, rolling hashes, composition lemma for c-universality. Bloom filters: 1-band, k-band. [L06] [Tb] video
2. 5. Multi-dimensional data structures. Range queries on binary search trees. K-d trees: basic principle, lower bound. Range trees: construction, queries. Dynamization by partial rebuilds. [L07] [M7] video
9. 5. Data structures for strings. Suffix array, suffix ranks, longest-common-prefix array. Applications: substring search, longest repeating substring, longest common substring of two strings. Construction of LCP array in linear time (Kasai's algorithm). Construction of suffix array in O(n log n) time by doubling. [L08] video
14. 5. Parallel data structures: PRAM/CRCW model, locking and issues with it, locking in binary search trees and (a,b)-trees. Atomic primitives. Lock-free stack, the ABA problem, memory management. Just for fun: The Deadlock Empire. [L09] video

Assignments

Description of assignments can be found in ReCodEx. You need to create an account there and sign up to a group for the recitations you chose.

Additional material (especially source code) is available as a Git repository. You can also browse it on the web.

Please submit your solutions to ReCodEx.

Exams

Please sign up in the Study information system. If no exam date suits you, please ask me about possibilities.

Class credit is required to pass the course, but it is not required for the exam.

There is a list of exam questions.

Literature

This page is maintained by Martin Mareš