SoSe 20: Data Structures
László Kozma
Additional information / Pre-requisites
Target Audience
Masters students in Computer Science or Mathematics, advanced Bachelor students.
Prerequisites
"Advanced Algorithms" or a similar class
Comments
Efficient data structures are important components of all nontrivial algorithms, and are basic building blocks of the modern computing infrastructure. Besides their practical importance, the design and analysis of data structures has revealed a rich mathematical theory. The ultimate theoretical limits of data structures are the subject of deep open questions.
The topic of this course is the design and analysis of data structures (including both classical and recent results), with emphasis on data structures that are adaptive, exploiting regularities in their input. One fresh topic is planned for each week. These include: self-adjusting trees and heaps, the geometry of comparison-based data structures, static and dynamic optimality, persistent-, succinct-, and external-memory- data structures, soft heaps and selection, pattern-avoidance, hashing and approximate counting, dynamic graph problems.
closeSuggested reading
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, 2nd Ed. McGraw-Hill 2001
- Tarjan: Data Structures and Network Algorithms, SIAM 1987
- recent articles
Links to similar courses at other universities:
- Pat Morin, Carleton, http://cglab.ca/~morin/teaching/5408/
- Erik Demaine, MIT, http://courses.csail.mit.edu/6.851/
- Jeff Erickson, UIUC, http://jeffe.cs.illinois.edu/teaching/datastructures/
- Venkatesh Raman, IMSc, https://www.imsc.res.in/~vraman/adsjan2012/index.html
27 Class schedule
Regular appointments