Data Structures I

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

Lectures are held every Wednesday from 9:00 [in room S5 if possible, otherwise online]. Sign up for recitations in SIS.

We will meet on Zoom, you should have received a Zoom link by e-mail. If you have not, check your spam folder and let me know. All lectures will be recorded and the videos posted here.

Please read the complete rules of the game.

date topics sources video
3. 3. Introduction: what is a data structure – interface vs. implementation, static vs. dynamic, model of computation. Examples of interfaces: queue, set, ordered set, dictionary. Flexible arrays (with both stretching and shrinking). [L01] video board
10. 3. Different approaches to amortized analysis: aggregation, accounting, coins, potentials. Examples: binary counters, deletion using tombstones, lazily balanced BB[α] trees. [L01] video board
17. 3. Splay trees: amortized analysis of the Splay operation. Incorporating splaying in Find, Insert, and Delete. [L02] [ST] video board
24. 3. Splay trees: Complexity of BST operations; remarks on static and dynamic optimality, sequential traversal, and working set bound. (a,b)-trees: definition, logarithmic height, Find, Insert, Delete, choice of parameters. [L02] [L03] video board
31. 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, sequential scanning of arrays. [L03] [L05] [CO] video board
7. 4. Cache-oblivious algorithms. 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 board
14. 4. 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. [L05] [CO] [STb] [L06] video board
21. 4. Hash function families: k-independence, constructions of universal/independent systems from linear functions. Generic bounds for composition of families, k-independent hashing from polynomials, tabulation hashing. Cuckoo hash tables. [L06] [Tb] [E10] video board
28. 4. Hash tables: open addressing, analysis of linear probing. [L06] [T] video board
5. 5. Hashing: lemmata on composition of hash function families. Hashing of vectors using scalar products. Bloom filters: 1-band, k-band. [L06] [Tb] video board
6. 5. Material covered at exercise classes: Hashing of vectors and strings using polynomials, rolling hashes. [L06] video board
12. 5. No lecture today – it's the rector's sporting day.
13. 5. Material covered at exercise classes: Optimization of Bloom filters, counting filters. [L06] video board
19. 5. Multi-dimensional data structures. Range queries on binary search trees. K-d trees: basic principle, lower bound. Range trees: construction, queries. Exercises: dynamization by partial rebuilds, speedup by fractional cascading. [L07] [M7] video board
26. 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 board
2. 6. Parallel data structures: locking in binary search trees and (a,b)-trees. Atomic primitives. Lock-free and wait-free data structures. Lock-free stack, the ABA problem, memory management. Just for fun: The Deadlock Empire. [L09] video board

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. Class credit is required to pass the course, but it is not required for the exam. If no exam date suits you, please ask me about possibilities.

There is a list of exam questions.

Literature

This page is maintained by Martin Mareš