Data Structures I (winter 2016)
Time and Place
Thursdays 9:00 to 10:30 in S10
Office hours
Mondays 15:00 to 16:00 in room 325 (or by email appointment in exceptional cases).
Topics and slides
Amortized complexity: binary counter, BB[α]-trees
Splay Trees
(a,b)-Trees
Red-Black Trees
Regular Heaps
Binomial Heaps
Fibonacci Heaps
Application of Heaps: Dijkstra’s Algorithm
External Memory Model vs. Cache-Oblivious Model
Page Replacement Strategies: Matrix transposition
Searching and Sorting: Mergesort, van Emde Boas tree layout, ...
Selecting a hash function: Universal Hashing
Collisions and their resolution
Cuckoo Hashing
Multidimensional Data Structures
kd Trees
Range Trees
Interval Trees
Segment Trees
R Trees
Homework assignments (deadlines)
External sorting (30.10)
Splay trees (13.11)
Fibonacci heaps (27.11)
Matrix transposition (11.12)
Hashing (1.1.2017)
For each exercise you can get up to 100 points. You need 350 points to pass.
Please carefully read the detailed rules!
See the results to your submissions.
Literature
A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.
T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009. On-line
K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984
D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005, Accessible on-line from faculty IP addresses.
D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.
E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.
R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.
M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.
M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.
D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: Algorithms and Applications, Springer, 3 rd edition, 2008. The second edition is on-line.
Erik Demaine: lecture Advanced Data Structures at MIT.
A summary of the course written by Vladimír Čunát.