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.
|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.||Plan: 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]|
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.
Please submit your solutions to ReCodEx.
- [CO] Erik Demaine: Cache-Oblivious Algorithms and Data Structures
- [E] Erik Demaine: přednáška Advanced Data Structures z MIT
- [H] Handbook of Data Structures and Applications (available online from MFF network)
- [Lxx] Martin Mareš: Lecture notes on data structures
- [M] Kurt Mehlhorn: Data Structures and Algorithms (digitální verze knihy)
- [ST] Sleator, Tarjan: Self-Adjusting Binary Search Trees, Journal of the ACM, 1985
- [T] Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing
- [Tb] Mikkel Thorup: High Speed Hashing for Integers and Strings