TUM - Chair VII - Foundations of Software Reliability and Theoretical Computer Science


	Practical Course: Algorithms for Programming Contests

News | Schedule | Content | Material

Please use the following e-mail address: conpra@in.tum.de.

Area

Computer Science III (Theoretical Computer Science)

Prerequisites

Basics of programming in C, C++ or Java, for instance from the lecture Introduction to Informatics 1
Lecture Fundamentals of Algorithms and Data Structures

Grading

To pass the practical course you need to solve enough of the exercise problems on your own and pass an oral examination in the end of the semester. The mark is computed using the quality and number of problems solved as well as the oral examination.

Description

Programming contests are competitions for solving problems with the help of computer programs. By taking part in these contests one may improve skills in using algorithms and data structures as well as in problem solving, software development and teamwork through fun and games. Important topics in computer science are combined with the fun in programming.

There are plenty of programming contests by now, each of them having a different mode and focus. The exercise problems in this course will be similar in style to the ones used in the International Collegiate Programming Contest (ICPC), an international programming contest for students which is run by the Association for Computing Machinery (ACM) since the 1970s. In this contest, groups of up to three students each need to solve eight to ten problems in five hours using one computer only. The Computer Science Department of TUM has been participating in the ICPC with multiple teams for several years.

A Some sample problem of our practical course gives an impression of the problems we are going to solve in this course. As the course doesn't require previous contest experience, and the tasks are solved by each student individually, the course uses easier problems than ICPC.

There will be a lecture where we explain algorithms for a new topic each week. During the following week, the participants need to solve problems related to this topic. Solutions, different ideas and remarks regarding the problems will be presented in the next lecture. The problems differ in the level of difficulty: There will be problems asking for straightforward implementations of the presented algorithms as well as harder problems taken from several contests. For submitting and judging the submissions we will use DOMJudge, the system which is used for almost all rounds of the ICPC.

Goals of this course are

a deep understanding of fundamental algorithms and data structures,
getting to know specialized algorithms used in current research,
improved skills in problem solving and problem analysis,
practice in recognizing needed algorithms for given problems on one's own,
improved capacities in teamwork by taking part in team contests,
the application of important mathematical techniques as well as
preparing the participants for programming contests.

Registration details

Due to circumstances, this semester we are a smaller team and the target practical course size is 30 students. For course registration, we use the matching system, and we ask the applying students to complete some preliminary tasks.

The amount of work taken into account is two problems (there are some easy ones in the list), and we will check progress before submitting the matching priorities (it is not too late as long as matching system is open for students).

We remind everyone that the practical course includes five programming problems of various complexity per week, and most of them are harder than the easy ones in the list. To demonstrate the prerequisite skills (and interest in the course), we ask the students wishing to register (both local and exchange students) to solve some problems in a similar format. As our internal platform is tied to the local TUM accounts, we use an established third-party platform for programming contest based in EU, SPOJ.

Procedure:

Register at SPOJ. No need to specify your real name if you do not wish to.
Solve and submit some of the problems from the list below. We expect everyone to solve at least two; we might have to use further progress for ranking in the matching system. Some problems are easy, some require more effort, and some benefit from having a bit of experience or background knowledge. To the best of our knowledge, all of the problems are solvable in any of C++, Java or Python 2 (PyPy).
To confirm that the account is created by a student applying for ConPra course, submit solutions that immediately print a wrong answer to the listed marker problems in the specified order.
Send an email with you full name and SPOJ account name (public profile link) to the course contact email, conpra@in.tum.de — please put ConPra and SPOJ in the beginning of the subject
Assign ConPra some priority in the matching system.
Once you are either registered for the course or no longer wish to be registered for the course, you may delete the SPOJ account if you wish.

Chosen problems (please solve and submit at least two, more might be taken into account, trying and failing to solve more problems will be evaluated no worse than not trying, problem order is random):

Marker problems, please submit code that immediately prints a wrong answer to the marker problems in this order (the same three problems are repeated twice):