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

Requirements:

• At least 12 assignments per 10 points
• 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
• 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. For example, std::vector is OK only if its capacity is fixed. When in doubt, ask your instructor.