Data Structures I

I am teaching English version of the course Data Structures I [NTIN066] in the summer semester of 2018/2019.

Lectures are held every Thursday from 9:00 in room S4. Sign up for recitations in SIS. The course is accompanied by optional practicals on Analysis of data structures.

Please read the complete rules of the game.

date topics sources
21. 2. 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]
28. 2. Different approaches to amortized analysis: aggregation, accounting, coins, potentials. Examples: flexible arrays, binary counters, lazily balanced BB[α] trees. Splay trees: description of the Splay operation, incorporating splaying in Find, Insert, and Delete. [L01] [L02] [ST]
7. 3. Splay trees: amortized analysis. Remarks on static and dynamic optimality, sequential traversal, and working set bound. [L02] [ST]
14. 3. (a,b)-trees: definition, logarithmic height, Find, Insert, Delete, choice of parameters. Amortized bounds for (a,2a-1) and (a,2a)-trees. Top-down splitting and joining, parallel (a,b)-trees. At the practicals: Equivalence between (2,4)-trees and left-leaning red-black trees. [L03]
21. 3. Heaps: binary and d-regular heaps, strict and lazy binomial heaps, Fibonacci heaps. Use in Dijkstra's algorithm. [L04]
28. 3. There is be no lecture.
4. 4. Memory hierarchy: a sketch of hardware caches (see examples of memory access timings), full/set associativity and aliasing, multiple cache levels. Theoretical models: I/O, cache-aware, cache-oblivious. Example: sequential scanning of arrays. Sorting: MergeSort, multi-way MergeSort, a remark on FunnelSort and lower bounds. [L05] [CO]
11. 4. Cache-oblivious algorithms: matrix transposition. Model versus reality: Sleator-Tarjan theorem on competitivity of LRU. [L05] [CO] [STb]
18. 4. Hashing: buckets with lists. Choice of hash functions: c-universal and k-independent systems of functions. Expected bucket size for c-universal systems. Constructions of universal/independent systems from linear functions. [L06]
25. 4. Hash function families: generic bounds for composition of families, k-independent hashing from polynomials, tabulation hashing. Cuckoo hash tables. [L06] [Tb] [E10]
2. 5. Hash tables: bounds for chaining, analysis of linear probing. [L06] [T]
9. 5. Hashing: hash functions for vectors and strings: scalar product, polynomials. Bloom filters: 1-band, k-band, counting filters. [L06] [Tb]
16. 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, speedup by fractional cascading. [L07] [M7]
23. 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]

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š