Lecturer: Zdeněk Sawa (room: EA413, e-mail: zdenek.sawa@vsb.cz)
- Recent information about the course will appear here during the semester.
During the semester, numbers of problems will be published on these www pages. These problems come from server Online Judge. Students will obtain point for solutions of these problems. There will be specified for each problem, how many points it is possible to obtain for a solution of this problem, and a date until which solutions of this problem could be submitted. There will be differences in number of points for different problems depending on the difficulty of the given problems.
Solutions should be sent by e-mail to zdenek.sawa@vsb.cz.
A program is considered to be a solution of a problem if after sending to onlinejudge.org server, an answer Accepted is received (and that also satisfies all additional conditions specified for this problem on the page containing list of the problems if there are some).
At the end of the semester, students will present their solutions and discuss them with the lecturer. In particular, statement of a problem and its solution should be discussed for these problems. It is expected that this will be approximately 5 minutes of discussion for one problem.
The definitive number of points obtained for submitted problems will be determined after these presentations.
If it is found out that a student is not an original author of submitted solution (because it was copied from another student, copied from some web page, generated by AI, etc.), the points for this problem won't be counted. Moreover, 20 points will be subtracted from already obtained points. If such cheating will be repeated, 50 points will be subtracted, and if cheating will occur third time, such student will not obtain a credit, not matter how many points student obtained before.
Remark: A program is considered to be copied also in the case when it was obtained by small modifications of its original source such as renaming of identifiers, a change of formatting, a change of order of functions or methods in the source code, separating parts of the code into separate functions, inserting a body a function into a place where it was originally called, unimportant changes in an order of some commands, etc., where the goal is just to obfuscate the it is a copied program.
The seminar is not ended with an exam. Students obtain all points only for the credit. It is necessary to obtain at least 51 points for solved problems.
- Slides (version from September 14, 2025): spr-en.pdf
The goal of the seminar is a better understanding of design, analysis, and implementation of algorithms, and a better understanding of standard techniques used for creating new algorithms (dynamic programming, greedy algorithms, backtracking, ...), and of some particular algorithms from different areas such as graph theory, number theory, combinatorics, game theory, and computational geometry. The emphasis will be on design of efficient algorithms from the point of view of computational complexity and on a efficient implementation of these algorithms.
List of topics discussed in the seminar:
- Introduction. Implementation of algorithms
- Recursive algorithms
- Dynamic programming
- Greedy algorithms
- Graph algorithms
- Combinatorics
- Number theory
- Computational geometry
One of the goals of the seminar is to prepare students for types of problems that typically occur in programming contests such as International Collegiate Programming Contest (ICPC).
You can find problems from this contest from previous years for example on the following address (there are also sample solutions and test data):
Server onlinejudge.org contains a big number of problems (several thousand). On this server, there is a system for evaluating solutions of these problem, similar to systems used in different programming contests. A user can register to this server and then submit his/her solutions there. The system tests these solutions and returns an answer whether the solution was accepted or not.
Students in the seminar should register to this server and try to solve different problems published here. Many problems discussed in this seminar are problems from this server.
- Skiena, S. S., Revilla, M. A.: Programming Challenges: The Programming Contest Training Manual, Springer, 2003.
- Cormen, T. H., Leiserson, R. L., Rivest, R. L., Stein, C.: Introduction to Algorithms, MIT Press 2001.
- Dasgupta, S., Papadimitriou, C., Vazirani, U.: Algorithms, McGraw-Hill Science/Engineering/Math, 2006.