TDDD95 Algorithmic Problem Solving
There are four lab assignments in the course:
The purpose of the labs is to:
- Understand and implement commonly used algorithms related to for example strings, graphs, and computational geometry.
- Create a well structured and reusable code library that you can use in the homework exercises and the problem solving sessions.
ExaminationThe examination of labs is divided into two parts:
- An automatic test of the correctness of the code. This is checked by submitting your code to the automatic judge Kattis. For every task in the lab assignment there is a corresponding problem in Kattis.
- A subjective examination of the quality of the code. This is checked by the examiner or lab assistant who reads the code and makes sure that it satisfies both the general requirements below and any task-specific requirements described on the lab pages.
A lab is submitted when the corresponding problem in Kattis is solved. Your latest submission is used when checking the quality of your submission. Unless you are instructed otherwise, complementary work is also submitted via Kattis.
The code should be commented and well structured. Every assignment has a suggested function/class with name, input parameters and return values. This is only a suggestion, you may find better ways of doing it as long as it solves the problem. Take a look at the GNU coding standard and the Google coding standard for inspiration.
Every function and class should be appropriately documented. The documentation should explain things that are not obvious from the code. The code together with the documentation should be enough to understand both what the codes does (and what it does not do) and how to use it. The course does not include a written exam nor lab reports, so it is with the documentation you show your understanding of the theory related to the assignments. Your documentation will also help you greatly during the problem solving sessions. Your documentation should at least include:
- Your name as the author.
- A short explanation of the problem solved. If the problem is well-known, it is sufficient to refer to the problem name.
- Time complexity of each algorithm and data strcture operation. Memory complexity should also be included if it is larger than the input size.
- Practical instructions on how to use the implementation. This includes any assumptions made with regards to parameter values etc, e.g. if an input list is assumed to be non-empty.
The ideal is that your algorithms and data structures are general and robust, but it is hard to achieve. The most important thing is that exceptional cases are handled, by for example throwing an exception, and that this is well documented.
Inofficial interpretation of requirements
Here are interpretations, applications and rules of thumb related to the requirements. This is not an exhaustive list!
- Separate your algorithm/data structure implementation from input/output handling. Read the input, call a solver, output the result. The algorithm should not be responsible for input/output.
- Your algorithms should not be specially designed for Kattis test cases.
- Divide your code into multiple files when appropriate. For example, do not paste Kattio.java into your own code.
- Comment appropriately. Do not obscure the code with too many comments. Do not state the obvious. Comment functions and blocks of code rather than individual lines. Be certain to document the API of your code library from a user perspective rather than developer perspective. Input, output and exceptions are the most important aspects.
- The lab assignments suggest an API. Use this unless you find something which at least as good with respect to reusability. The API should not be designed explicitly for Kattis.
- Every student should submit to Kattis!
Page responsible: Fredrik Heintz
Last updated: 2021-01-04