Data Structures I — The Rules of the Game

Course structure

There are lectures and recitations (practicals).

To pass the course, you need to pass an exam (written/oral, covers theory) and get class credit from the recitations.

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

Overview:

• There are at least 8 programming assignments per 10 points
• and at least 4 experimental assignments per 15 points
• You need 90 points 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
• C++ and (usually) Python available

Experimental assignments:

• Measure properties of a given implementation
• Write a report (and submit PDF)

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