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.

date topics sources video
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.

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.


This page is maintained by Martin Mareš