Data Structures 1 (practicals)

Time and space coordinates:

Tuesday 10:40, S10

This practicals are taught by David Mareček

The lectures are taught by Petr Gregor on Mondays at 15:40 in S3 (link to the lectures page)

(the other parallel practicals taught by Jirka Fink are in Fridays 12:20)

LECTURE NOTES

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 points in total).

Assignments:

All assignments are submitted using the 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 assignment.
Instructor's feedback on your solutions will also be in ReCodEx (it 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
- The instructor looks at the source code
- C++ and Python are available
Experimental assignments:
- Measure properties of a given implementation
- Write a report (and submit PDF)
  - Make sure that the figures are properly labelled.
  - Describe the plots: are the curves asymptotically constant/logarithmic/linear?
  - Explain why: cite the theorem supporting your observation, or try to prove it yourself. Or at least try to guess. (In some cases it is harder to prove it.)
  - Compare the curves among each other and among the experiments. Try to explain the differences.
General 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 the deadline, you can re-submit.
- The code must pass all tests.
- The quality of your code and reports contributes to grading.
- Do not use non-trivial code you didn't write yourself. This includes other peoples' implementations and non-obvious 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 in the lecture, citing the lecture is considered sufficient.

Practicals:

Attendance at the practicals is not mandatory but recommended.
The practicals will usually have three parts:
- Discussing the homework: solution of the previous assignment, questions about the current assignment, and explanation of the next assignment
- Discussing questions and issues from the lecture
- Other exercises that should help you better understand the topic

20th February: HW: tree_successor, exercises, solutions

27th February: HW: splay_operation, Splay-Trees demo, exercises, solutions

12th March: HW: splay_experiment (subset test example), exercises, solutions

19th March: HW: ab_tree, B-Trees demo, exercises, solutions

26th March: HW: ab_experiment (deadline in 3 weeks, if you want a feedback, submit before April 9th)

2nd April: Splay-experiment solution, Red-Black Trees demo, cache models

9th April: HW: matrix_transpose, exercises, solutions

16th April: HW: matrix_experiment, exercises, solutions

23rd April: (a,b)-experiment solution, HW: cuckoo_hash, exercises, solutions

30th April: HW: find_duplicates

7th May: HW: kgrams, exercises

14th May: CANCELLED (Rector's Sports Day)