Data Structures I, practicals — The Rules
- Basic algorithms and data structures:
e.g., balanced search trees (AVL/red-black/…)
- Discrete math (combinatorics, basic number theory)
- Basic probability theory (linearity of expectation, …)
If you are missing any of these, please ask for help soon.
- At least 12 assignments per 10 points will be assigned
- 80 points needed for class credit
- Deadline: 2 weeks (longer at the end of semester)
- You are given a partial implementation of a DS
- Implement the missing bits
- Automatic checking, tests are public
- Instructor looks at the source code
- Passing the automatic tests is only a necessary condition, implementation must
be also correct (correct complexity, do not violate structure invariants, …)
- You may modify the given partial implementation
- C++ and Python available
- Measure properties of a given implementation
- Write a report (and submit PDF)
- Use theory from the lectures to explain results (if possible)
- 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.
std::vector is OK only if its capacity is fixed.
When in doubt, ask your instructor.
- The previous rule includes code from the internet, e.g. from
StackOverflow. Be careful and do not break this rule by accidentally copying code you
saw. Searching how to use Python list on the internet is probably harmless, searching how
to implement a splay tree is probably not — use lecture notes instead. When in doubt, ask
- Cite your sources! (Especially in the reports.) Using others people
work without citing it is a serious violation of academic ethic code.
- If you decide to implement a different version of the data structure than the
one described in the lecture we require a proof that your version has the same properties.