Lectures Automata and formal languages Efficient Algorithms and
Data Structures I Randomized Algorithms Parallel Algorithms Seminar Selected Topics in Efficient Algorithms Lab Course Algorithms for Programming Contests

Practical Course: Algorithms for Programming Contests

Lecturer
Prof. Dr. Ernst W. Mayr
Teaching Assistant
Stefan Toman
Chris Pinkau
Philipp Hoffmann
Christian Müller
Please use the following e-mail address: conpra@in.tum.de.
Module
IN0012, IN2106, TUMonline
Preliminary Discussion
The preliminary discussion will take place on Thursday, June 26, 14:30 in room MI 00.13.009A.
Time and Place
Thursdays, 12:00 - 13:30, room MI 00.08.038 NEW
Computer Room
The problems may be solved using our computer room MI 03.09.034, the "Rechnerhalle" or your own computer.
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 excercise problems on your own and pass an oral examination in the end of the semester. The mark is computed using the quality and amount of problems solved as well as the oral examination.

Problem Sets

General Information
Information Sheet - Judge - A Script Written by Students NEW (Please note that this script is not checked by us and may be incorrect/incomplete.)
Week 1: Minimum Spanning Trees
Problem Set - Further reading - Sample Solution for Space Travel - Survey
Week 2: Shortest Paths
Problem Set - Further reading - Survey
Week 3: Flows
Problem Set - Further reading - Survey
Week 4: Data Structures I
Problem Set - Further reading - Survey
Week 5: Data Structures II
Problem Set - Further reading - Survey
Week 6: Brute Force/Backtracking
Problem Set - Survey
Week 7: Dynamic Programming
Problem Set - Further reading (Edit Distance) - Further Reading (Cyclic Longest Common Subsequence) - Further Reading (Longest Increasing Subsequence) - Survey
Bonus: NWERC 2014
This week you may participate in the NWERC 2014 Open Contest. Participating in this contest is absolutely voluntary, but you may get bonus points. To participate, create an account at https://open.kattis.com/login and join the contest at https://open.kattis.com/contests. The contest starts this Sunday, 30.11.2014, 11:00 a.m. CET and will last for five hours. You will find the problems on the Kattis website and may upload your submissions there. If you solved a problem on the Kattis website, send a clarification to our judge (the one where you submit all your homework) containing the problem ID, your source code and your user name on the Kattis website. We will check your submission and award 6 bonus points for each problem solved.
Week 8: Approximation Algorithms
Problem Set - Further reading (Colouring) - Further reading (TSP) - Survey
Week 9: Online Algorithms
Problem Set - Further watching for problem WS09N09A WS09N09B WS09N09C WS09N09D WS09N09E - Survey
Week 10: Number Theory
Problem Set - Survey
Week 11: Geometry
Problem Set - Survey
Week 12: Projective Geometry
Problem Set - Survey
Week 13: Contest
Problem Set - Survey

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 excercise problems in this course will be similar 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. Some sample problems of the German Collegiate Programming Contest (GCPC) 2012 give an impression of the problems we are going to solve in this practical course.

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.