AAPS Advanced Algorithmic Problem Solving
There are four lab assignments in the course:
In the labs you will:
- Create a well structured and reusable code library by implementing commonly used algorithms related to for example strings, graphs, number theory, and computational geometry.
- Demonstrate the reusability of your code library by finding and solving additional algorithmic problems.
The purpose of the labs is to:
- Understand and implement commonly used algorithms related to for example strings, graphs, number theory, and computational geometry.
- Create a well structured and reusable code library that you can use in the homework exercises and the problem solving sessions.
The examination of labs is divided into three 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 who reads the code and makes sure that it satisfies the requirements (see below).
- An optional examination of the reusability of the code. To show the reusability of the code library a student may send a list of problems solved using the code library together with short comments what changes were made to the code library or how the problem was transformed into a problem that could be solved with the code library. The correctness of the solutions should be verified either by Kattis or by UVA. For each of the four lab assignment a total of 3 points can be awarded towards the grade on LAB1.
A lab is submitted when the corresponding problem in Kattis is solved. We will check the quality of the code in the SVN repository and the latest submission to Kattis before the recommended deadline and on request from you.
You should keep your code library in the SVN repository provided to you. This is the code that you will be allowed to use in the problem solving sessions. Only code that you have written yourself is allowed in the code library.
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 authors' names should be clearly stated in a comment in the beginning of the code.
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 functionality from input/output. 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. 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.
- The names of the author(s) should always be stated in the beginning of each file, also header files and early submissions.
- Every student should submit to Kattis!
Page responsible: Fredrik Heintz
Last updated: 2013-02-04