Data Structures 1 (practicals)
Time and space coordinates:
Wednesday 9:00, S8
Wednesday 12:20, S1
Both practicals are taught by David Mareček
The lectures are taught by Petr Gregor on Mondays 12:20 in S5 (link to the lectures page)
Passing requirements:

To get the credit you need at least 75 points from homework assignments.

There will be 7 programming assignments per 10 points and 3 experimental assignments per 15 points. (i.e. 115 point in total).
Assignments:

All assignments are submitted using ReCodEx system (including the experimental ones).

Please join the ReCodEx group corresponding to these practicals.

You will have at least 14 days to complete each of the assignment.

Instructor's feedback to your solutions will also be in ReCodEx (can be useful to set up mail notifications).

Materials for assignments (source codes etc.) will be published to the git repository.

Programming assignments:

You are given a partial implementation of a DS

Implement the missing bits

Automatic checking, tests are public

Instructor looks at the source code

C++ and Python available

Experimental assignments:

Measure properties of a given implementation

Write a report (and submit PDF)

Rules:

Feel free to talk about assignments with other people, but do not share code nor reports (except with the instructor).

Do not share example solutions with anybody.

Deadlines are strict.

Before deadline, you can resubmit.

The code must pass all tests.

Quality of your code and reports contributes to grading.

Do not use nontrivial code you didn't write yourself. This includes other peoples' implementations and nonobvious library functions. Trivial cases of growing arrays (appending to
std::vector
in C++ or list.append()
in Python) are permitted, anything more complicated isn't. When in doubt, ask your instructor.

All theorems used in your reports must be stated in full and their source must be properly cited. If the theorem was stated at the lecture, citing the lecture is considered sufficient.
Practicals:

Attendance at the practicals is not mandatory but recommended.

The practicals will ususally have three parts:

Discussing the homeworks: solution of the previous assignment, questions about the current assignment, and explanation of the next assignment

Discussing questions and issues from the lecture

Another exercises that should help you better understand the topic
16th February: exercises, solutions
23rd February: exercises, solutions, SplayTrees demo
2nd March: exercises, solutions, Assignment 3: subset example on n=10000 elements
9th March: BTrees demo, B+Trees demo, Red/Black Trees demo
16th March: topdown delete and insert in (a,b)Trees (see the lecture notes), Heap demo
23rd March: HW: matrix_transpose, exercises, solutions, cacheoblivious algorithms
30th March: 2universality of MultiplyShift hashing (see page 277 here, so far in Czech only), linearity of expectation
6th April: HW: cuckoo_hash, exercises, solutions
13th April: 3independence of Tabulation Hashing, the universality of L and L' family
20th April: HW: hash_experiment, overview of hashing families, 2independent multiplyshift
27th April: HW: find_duplicates, Bloom filters, counting filters, rolling hashes
4th May: HW: kgrams, Kasai's algorithm for building LCP, Doubling algorithm for building Suffix arrays (seek time 1:21:25), bucket sort
11th May: cancelled  Rector's day
18th May: Multidimensional range trees, dynamization, fractional cascading