TDDD95 Algorithmic Problem Solving
Course information
Registration
To participate in the course, you must register in three different systems.- LADOK registration using the LADOK student pages opens on January 15.
- Webreg is used to track your progress for labs and problem solving sessions. Note that you must register for both.
- Kattis is used to submit and test your implementations (see below). Register using the "I am a student taking the course and I want to register for it on Kattis" option on the Kattis course page.
Kattis
To automatically check whether your programs are correct this course uses the automatic judge Kattis. It allows you to submit programs to check whether they solve a partiular problem almost immediately. To receive points for your submissions, you must register for the course in Kattis by pressing "I am a student taking this course and I want to register for it on Kattis".
As a student at Linköping University you should be able to log in to Kattis using your LIUID and associated password. If this does not work, please contact the examiner.
Kattis is continually being improved, but has so far been very reliable. There is some limited documentation, which should answer most of the questions you have. There are also two tutorials that will show you how to get started. We recommend that you go through these before you start the course. Advice:
- If you use Java, then the class with the main method must be public.
- Input in C++ using cin from iostream can be surprisingly slow for problems involving a lot of IO (~1 MB or more). The Kattis help pages has information on how to alleviate this without having to use the more cumbersome C stdio routines.
- Input in Java is also quite slow if handled incorrectly, but Kattis provides a special IO class that can help you. The Kattis help pages has more information.
- If your solution outputs a lot of data, make sure that you avoid flushing the output buffer except when necessary. In C++, prefer "\n" over std::endl, and instead include a single std::flush at the end of your program. In Java, prefer print("\n") instead of println(), and end your program with a single flush() call.
Programming languages
You are free to use any programming language Kattis supports. However, we recommend that you use either C++ or Java, as we cannot guarantee that all problems are solvable using other languages. In particular, Python should be fine for most problems, but there might be problems where Python is inherently too slow. If you choose any other language than the three already mentioned, we cannot provide you with any language-related assistance. Comparing C++ and Java, the former tends to be faster than the later by a factor two or more. On the other hand, Java's memory model is less error prone, and it has a very comprehensive standard library. The performance difference is also not that significant in the context of this course, since you will most often pass way below the time limit if your solution has the intended time complexity. The choice is yours, but consider that the course covers a lot of material, and you will write a significant amount of code. Our recommendation is therefore that you choose the language you're most comfortable with, since it will let you focus on the data structures and algorithms rather than learning the quirks of a new language.
We strongly recommend that you familiarize yourself with a potent debugger for your chosen language. Debuggers are much more powerful tools than debug prints and other basic debugging techniques. Using a debugger enables you to e.g. pause the execution of your program on a specific line or if an arbitrary condition is met, print the stack trace, inspect arbitrary variables during run-time, and much more. Some good command-line debuggers are GDB (C++), jdb (Java), and pdb (Python). These debuggers are well established, and there are many good tutorials available online. Most IDEs also come with graphical debugging tools.
Finally, if you choose to implement your programs in C++, you should familiarize yourself with at least the basic functionality of valgrind. In addition to finding memory leaks, valgrind also performs various memory consistency checks, and can e.g. issue warnings if you forget to initialize a variable, or if you try to access invalid indices of a vector. Such errors commonly don't result in compilation or run-time errors, but might mean that your program gives incorrect solutions.
Page responsible: Fredrik Heintz
Last updated: 2024-01-05