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 fall semester 2020 is „Quantum Computing“. This seminar is intended for Bachelor's students. If you are interested in participating in this seminar, please write an email to Alexander Moch. The registration deadline is 5 October 2020.

    • Fall 2020 (Bachelor): Quantum Computing

      In this seminar we will look at how a quantum computer operates. We will look at the computation model as well as algorithms and compare the algorithms' running time to that of a classical computer.

      The prerequisite for this seminar is the course Lineare Algebra I. For some topics it may be beneficial to have attended Algorithmen und Datenstrukturen, Kryptografie I or Theoretische Informatik.

      If you are interested in participating in this seminar, please take a look at the book by Yanofsky and Mannucci mentioned below. It will serve as the main source of information for the seminar.

      As an introduction into the topic, I can recommend this talk by Microsoft Research:
      https://www.youtube.com/watch?v=F_Riqjdh2oM

      The seminar is intended to take place in German, though you may use English for your talk. If you are interested in participating in this seminar, please write an email to Alexander Moch. The registration deadline is 5 October 2020.

      Literature:

      Quantum Computing for Computer Scientists (2008)
      by Noson S. Yanofsky and Mirco A. Mannucci.

      eBook available in the university's library:
      https://primo.bib.uni-mannheim.de/permalink/f/19ojnqi/MAN_CUPCR9780511813887

      Topic Selection:

      The topics will be based on the chapters of the book by Yanofsky and Mannucci. I will update the topic selection as soon as I have decided on how to structure the seminar.

      Registration:

      Please register by 5 October 2020 via email to Alexander Moch

      The seminar is meant for up to 10 participants. If the number of registrations exceeds 10, the participants will be selected based on their previous grades.

    • 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