SIS code: 
Semester: 
summer
E-credits: 
6
Examination: 
2/2 Z+Zk
Instructor: 
Instructor: 
Petr Gregor

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 re-submit.
    • The code must pass all tests.
    • 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 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, Splay-Trees demo

2nd March: exercises, solutions, Assignment 3: subset example on n=10000 elements

9th March: B-Trees demo, B+Trees demo, Red/Black Trees demo

16th March: top-down delete and insert in (a,b)-Trees (see the lecture notes), Heap demo

23rd March: HW: matrix_transpose, exercises, solutions, cache-oblivious algorithms

30th March: 2-universality of Multiply-Shift hashing (see page 277 here, so far in Czech only), linearity of expectation

6th April: HW: cuckoo_hash, exercises, solutions

13th April: 3-independence of Tabulation Hashing, the universality of L and L' family

20th April: HW: hash_experiment, overview of hashing families, 2-independent multiply-shift

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: Multi-dimensional range trees, dynamization, fractional cascading