LEA

Practical Course: Algorithms for Programming Contests

  • Lecturer
    Prof. Dr. Harald Räcke
  • Teaching Assistant
    Stefan Toman
    Chris Pinkau
    Moritz Fuchs
    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 Monday, July 6 at 10:00 a.m. in room 5620.01.102 (102, Interims Hörsaal 2).
  • Time and Place
    Wednesday, 12:00 p.m. - 1:30 p.m., Room MI 00.08.038

    Caution: On December 2, 2015 the lecture will be held in room 00.13.009A.
  • 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
  • Week 1: Introduction
    Problem Set - Information about TUMjudge - Survey
  • Week 2: Data Structures I: Union-Find, Binary Search
    Problem Set - Further Reading - Survey
  • Week 3: Minimum Spanning Trees
    Problem Set - Further Reading - Survey
  • Week 4: Shortest Paths
    Problem Set - Further Reading - Survey
  • Week 5: Flow
    Problem Set - Further Reading - Survey
  • Week 6: Brute Force/Backtracking
    Problem Set - Survey
  • Bonus: Amirkabir 2015
    This week you may participate in the Amirkabir ICPC 2015. Participating in this contest is absolutely voluntary, but you may get bonus points. You may participate in teams of up to three students. The contest starts Friday, 20.11.2015, 12:00 a.m. CET (please be there 30-60 minutes earlier) at room MI 02.07.038 and will last for five hours. All information about the contest may be found at http://icpc.tum.de/news/auticpc15. We will award 4 bonus points for the first two problems solved (each) and two more bonus points for each further problem solved to each team member. You may also team up with students of TUM that are not participating in this course!
  • Week 7: Greedy
    Problem Set - Further Reading (Greedy and Matroids) - Further Reading (Greedy and Approximation) - Survey
  • Bonus: NWERC 2015
    This week you may participate in the online contest of NWERC 2015, the official regional contest of the ACM ICPC. Participating in this contest is absolutely voluntary, but you may get bonus points. You may participate in teams of up to three students. The contest starts Sunday, 29.11.2015, 10:00 a.m. CET online at https://open.kattis.com/contests/nwerc15open. You need to register a Kattis account to participate. We will award 4 bonus points for the first two problems solved (each) and two more bonus points for each further problem solved to each team member. You may also team up with students of TUM that are not participating in this course! To claim the points please write a clarification containing your team name and the number of problems you solved.
  • Week 8: Dynamic Programming
    Problem Set - Further reading (Edit Distance) - Further Reading (Cyclic Longest Common Subsequence) - Further Reading (Longest Increasing Subsequence) - Survey
  • Week 9: Data Structures II: Big Integers/Rationals, Tries
    Problem Set - Survey
  • Week 10: Number Theory
    Problem Set - Survey
  • Week 11: Contest
    Problem Set - Survey
  • Week 12: Geometry
    Problem Set - Survey
  • Week 13: Projective Geometry
    Problem Set - Survey
  • Week 14: Contest
    Problem Set - Survey
  • Bonus: Wintercontest 2016
    This week you may participate in the FAU Wintercontest 2016. Participating in this contest is absolutely voluntary, but you may get bonus points. You may participate in teams of up to three students. We will provide food and drinks for all participants. The event starts Saturday, 30.01.2016, 10:30 a.m. CET at the computer labs ("Rechnerhalle"). All information about the contest may be found at http://icpc.tum.de/news/wintercontest16. We will award 4 bonus points for the first two problems solved (each) and two more bonus points for each further problem solved to each team member. You may also team up with students of TUM that are not participating in this course! Remote participation is not possible.

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 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 sample problem of our practical course gives an impression of the problems we are going to solve in this 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. For submitting and judging the submissions we will use TUMjudge, a fork of a system which is used for many 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.