Data Structures 1

Data Structures 1 - tutorial

This page is dedicated to the tutorial sessions of Data Structures 1 (NTIN066) with the lectures given by Michal Koucký.
The tutorials take place every Friday at 12:20 in the room S7 (Malá Strana building, second floor).
If you have any questions, or you would like to consult something, send me an email to chmel(a half of an AT-AT)iuuk.mff.cuni.cz.
Attendance at the tutorials is voluntary but recommended. We will talk about previous homework solutions, questions regarding the topics from the lecture, and, if time permits (and it usually does), we will solve theoretical exercises for better understanding of the discussed data structures.

Credit requirements

To get the class credit, you have to earn at least 75 points, and we guarantee that homework assignments for at least 115 points will be made available.

Homework

The rules can be found in more detail here (but please note that the number of assignments and the required points for the credit differ). I would also like to point out the last two points regarding the use of AI.

In short: after almost every tutorial, an assignment will be given. In total, we guarantee that at least seven programming assignments (10 points each) and three experimental assignments (15 points each) will be given. For each assignment, you will have two weeks to solve it. All assignments are handed in solely through ReCodEx. You can find the assignments on the GitLab of the Department of Applied Mathematics here.

Estimated schedule and history

Date	Contents
21. 2. 2025	Introduction and some revision: Dijkstra and heaps, asymptotics and binary search trees. Exercises. Solutions of the exercises. We started with an introduction of the subject and some prerequisites. Then, we talked about the requirements for obtaining the class credit and we have assigned the homework `tree_successor` with its deadline on 7. 3. 2025 at 23:59. (Overall, we agreed on the deadline for homework to be the midnight between Friday and Saturday two weeks after assigning the homework.) Then, we worked on solving the exercises, and in the end, we have gone through exercises 1 to 3.
28. 2. 2025	Amortized analysis. Exercises. Solutions of the exercises. We talked about amortized analysis throughout the whole tutorial: we mentioned the aggregate method, the coin method and the potential method. We have gone through exercise 1 in full detail and mostly through exercise 2. We will return to exercise 2 quickly next tutorial to finish it properly.
7. 3. 2025	Splay trees. Exercises. A splay trees recap by Ondra Mička, visualisation, solutions of the exercises. First, we assigned the homework `splay_operation` with its deadline on 21. 3. 2025 at 23:59. Then, we finished exercise 2 from last time, and we have gone through exercises 2 and 3, making sure that we understand the differences between the standard and naive splay.
14. 3. 2025	Plan: Continuation of splay trees. Exercises.