Selected Topics of Theoretical Computer Science and Cryptography

The seminar „Selected Topics of Theoretical Computer Science and Cryptography“ addresses current topics from the fields of complexity theory, algorithms and cryptography. It takes place in each semester, optionally in German or English.

Prerequisites for participation are the following Bachelor courses from the University of Mannheim or equivalent courses from other universities: Formal Foundations of Computer Science, Practical Computer Science I and II, Algorithms and Data Structures and Theoretical Computer Science or Cryptography I, respectively. Exceptionally, the prerequisite of the courses Theoretical Computer Science or Cryptography I can be disregarded. In this case, necessary prior knowledge of these areas will be imparted during the course of the seminar.

The topic description as well as organizational information about registration and execution of the seminar of the respective semester will be published on the website of the working group before the start of the semester.

The topic for the spring semester 2020 is „Advanced Algorithms for Flow and Matching Problems“. This Seminar is intended for Master's students.

    • Spring 2020 (Master): Advanced Algorithms for Flow and Matching Problems

      Flow- and Matching Problems occur in many real-life applications and the search for efficient algorithms for these types of problems represent a central topic in Combinatorial Optimization. In the Algorithmics course we discussed already basic Flow- and Matching algorithms like the Ford-Fulkerson method and the Edmonds Karp algorithm for the Maximum Flow Problem and MaxFlow-based algorithms  for the Maximum Matching Problem for undirected bipartite graphs.

      In this seminar we go some steps further and will deal with some more advanced algorithmic approaches leading to more efficient algorithms for more general types of Flow- and Matching problems. In this context, the modelling of Flow- and Matching problems as special instances of primal and dual linear programming will play an important role.

      Literature: „Combinatorial Optimization“ by William J. Cook, William H.  Cunningham, William R. Pulleyblanc, Alexander Schrijver, John Wiley and Sons 1998, Chapters 1-5

      Topic Selection

      • Push-Relabel Maximum Flow Algorithms
      • Algorithms for Multicommodity Flows
      • Primal- and Dual Minimum Cost Flow Algorithms
      • Maximum Matching for general undirected graphs
      • Minimum Weight Perfect Matching for bipartite weighted undirected graphs
      • Minimum Weight Perfect Matching for general weighted undirected graphs
      • ...
    • Fall 2019 (Bachelor): Complexity Theoretical Classification of Games

      Enthusiasm for games with two or more participants has been an integral part of human social life for many centuries. Generally, everyone knows games that are simple (or „boring“) in the sense that there are few different game sequences only and accordingly little room for creative and unexpected game ideas. In contrast to this, there are complex (or „demanding“ or „interesting“) games, such as chess or go, for whose successful completion one can go to the limit of human intelligence and creativity.

      We will deal with methods for formally determining whether a game is „boring“ or „interesting“ by the means of its set of rules. As a basis for this, we consider the problem of finding a winning strategy from a given game situation. To start with, this problem is to be formally described as a computational problem. In a further step, we then concentrate on methods to determine the complexity of this problem with regard to the schema of best-known complexity classes P, NP, PSPACE, etc. Besides elementary studies of computer science, preferable prerequisite for this seminar is the course Theoretical Computer Science. However, if required, the acquisition of basic complexity theoretical knowledge will be guided throughout the course of the seminar.

      Registration via e-mail to Alexander Moch until September 2nd, 2019. Further information will then be provided by e-mail.

      Topic Selection