Data Structures I, practicals — The Rules

Requisite knowledge

• Programming
• 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.

Assignments

Requirements:

• 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)

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
• 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

Experimental assignments:

• Measure properties of a given implementation
• Write a report (and submit PDF)
• Use theory from the lectures to explain results (if possible)

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 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. For example, 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 your instructor.
• 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.