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

1. Search Trees

   • Amortized complexity: binary counter, BB[α]-trees

   • Splay Trees

   • (a,b)-Trees

   • Red-Black Trees

2. Heaps

   • Regular Heaps

   • Binomial Heaps

   • Fibonacci Heaps

   • Application of Heaps: Dijkstra’s Algorithm

3. Memory Hierarchies

   • External Memory Model vs. Cache-Oblivious Model

   • Page Replacement Strategies: Matrix transposition

   • Searching and Sorting: Mergesort, van Emde Boas tree layout, ...

4. Hashing

   • Selecting a hash function: Universal Hashing

   • Collisions and their resolution

   • Cuckoo Hashing

5. Multidimensional Data Structures

   • kd Trees

   • Range Trees

   • Interval Trees

   • Segment Trees

   • R Trees

Homework assignments (deadlines)

1. External sorting (30.10)

2. Splay trees (13.11)

3. Fibonacci heaps (27.11)

4. Matrix transposition (11.12)

5. Hashing (1.1.2017)

Submission server.

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

1. A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011.

2. T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009. On-line

3. K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984

4. 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.

5. D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. J. ACM 32 (3): 652–686, 1985.

6. E. Demaine: Cache-Oblivious Algorithms and Data Structures. 2002.

7. R. Pagh: Cuckoo Hashing for Undergraduates. Lecture note, 2006.

8. M. Thorup: High Speed Hashing for Integers and Strings. lecture notes, 2014.

9. M. Thorup: String hashing for linear probing (Sections 5.1-5.4). In Proc. 20th SODA, 655-664, 2009.

10. D.E. Knuth: The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998

11. 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.

12. Erik Demaine: lecture Advanced Data Structures at MIT.

13. A summary of the course written by Vladimír Čunát.

Other links

• Czech lecture.

• Last year's Czech and English lectures.