News
Delayed presentationWritten on 16.03.21 by Antoine Joux The following presentation that was delayed will take place tomorrow: March 17th, 2021 10:30 : Randomized / probabilistic algorithms  Macean, Krisztian
If it is possible for you, please attend the presentation in the usual zoom room.

Timetable for the second presentations (updated)Written on 18.01.21 (last change on 16.03.21) by Antoine Joux The second presentations will be on January 25th and February 1st, according to the following schedule: January 25th, 2021: 14:00 : Sort algorithms  Karim, Assiri Nassirou 14:30 : P versus NP  Meyer, Joshua 15:00 : Computation models  Hennen, Pascal 15:30 : Graph algorithms… Read more The second presentations will be on January 25th and February 1st, according to the following schedule: January 25th, 2021: 14:00 : Sort algorithms  Karim, Assiri Nassirou 14:30 : P versus NP  Meyer, Joshua 15:00 : Computation models  Hennen, Pascal 15:30 : Graph algorithms  Bäumel, Tanja
February 1st, 2021 14:00 : Interactive proofs  Seyler, Luc 14:30 : GCD algorithms  Wagmann, David
March 17th, 2021 10:30 : Randomized / probabilistic algorithms  Macean, Krisztian 
Timetable for the first presentationsWritten on 16.11.20 by Antoine Joux The first presentations will be on December 7th and 14th, according to the following schedule: December 7th, 2020: 14:00 : Computing with Circuits  Kaufmann, Jonas 14:30 : Randomized / probabilistic algorithms  Macean, Krisztian 15:00 : Sort algorithms  Karim, Assiri… Read more The first presentations will be on December 7th and 14th, according to the following schedule: December 7th, 2020: 14:00 : Computing with Circuits  Kaufmann, Jonas 14:30 : Randomized / probabilistic algorithms  Macean, Krisztian 15:00 : Sort algorithms  Karim, Assiri Nassirou 15:30 : Computation models  Hennen, Pascal
December 14th, 2020: 14:00 : Graph algorithms  Bäumel, Tanja 14:30 : Interactive proofs  Seyler, Luc 15:00 : GCD algorithms  Wagmann, David 15:30 : P versus NP  Meyer, Joshua

Topic assignationWritten on 09.11.20 by Antoine Joux Following our meeting today, the topics have been assigned as follows: Topic A : Computation models  Hennen, Pascal Topic B : P versus NP  Meyer, Joshua Topic C: Randomized / probabilistic algorithms  Macean, Krisztian Topic D : Interactive proofs  Seyler, Luc Topic E :… Read more Following our meeting today, the topics have been assigned as follows: Topic A : Computation models  Hennen, Pascal Topic B : P versus NP  Meyer, Joshua Topic C: Randomized / probabilistic algorithms  Macean, Krisztian Topic D : Interactive proofs  Seyler, Luc Topic E : Sort algorithms  Karim, Assiri Nassirou Topic F : Computing with Circuits  Kaufmann, Jonas Topic G : Graph algorithms  Bäumel, Tanja Topic H : GCD algorithms  Wagmann, David Topic I : Polynomial multiplication  Unassigned Topic J : Primality testing  Unassigned 
Algorithms and Complexity
Description
This proseminar is meant to provide students an overview over foundational results in the area of algorithms and complexity. As a proseminar's primary purpose is to learn presentation skills, the seminar will feature two presentations from each student.
Because of the Covid19 situation, this proseminar will be organized via a visioconference system.
After each presentation, the fellow students and lecturers will provide feedback on how to improve the presentation. This general feedback must then be taken into account for the second block of the course, where again each student will present.
For the first presentation, the student will present one of the proposed topics (based on one or two of the suggested references).
To not bore the audience, the second presentation will be on a related topic and based on a different reference document (book or research article).
This second reference will be chosen by the students (not from the initial list of references) and the relevance of the choice will be part of the grading of the second presentation.
The first presentations will count towards 30% of the overall grade, the choice of the second reference will count for 30% and the second presentation itself will count for the remaining 40% of the overall grade. Attendance in the proseminar meetings is mandatory. Because of the block structure, any absence needs a doctor's note as justification.
References
[1] Arora and Barak. Computational Complexity : A Modern Approach.
http://theory.cs.princeton.edu/complexity/book.pdf
[2] Introduction to Algorithms (3rd edition). Cormen, Leiderson, Rivest, Stein.
[3] Algorithms and Complexity. Wilf. Internet edition available at https://www.math.upenn.edu/~wilf/AlgoComp.pdf
[4] Complexity of Algorithms. Gacs and Lovasz. Internet edition available at http://web.cs.elte.hu/~lovasz/complexity.pdf
[5] Lecture Notes on Computational Complexity. Trevisan. Internet edition available at https://people.eecs.berkeley.edu/~luca/notes/complexitynotes02.pdf
The references are available from the library :https://www.infomathbib.de/tmp/vorlesungen/infoadvanced_algorithms_and_complexity.html
List of topics
Topic A : Computation models
[1]  Chapter 1
[4]  Chapter 2
Topic B : P versus NP
[1]  Chapter 2
[2]  Chapter 34
[3]  Chapter 5
[4]  Chapter 6
[5]  Chapter 1
Topic C: Randomized / probabilistic algorithms
[1]  Chapter 7
[2]  Chapter 5
[4]  Chapter 7
[5]  Chapter 5 and 6
Topic D : Interactive proofs
[1]  Chapter 8
[4]  Chapter 14
[5]  Chapter 13 (+14)
Topic E : Sort algorithms
[2]  Part II
[3]  Section 2.2
Topic F : Computing with Circuits
[1]  Chapter 6
[4]  Chapter 16
[5]  Chapter 4
Topic G : Graph algorithms
[2]  Part VI
[3]  Chapter 3 (+2.3)
[4]  Section 4.4
Topic H : GCD algorithms
[2]  Chapter 31
[3]  Chapter 4
Topic I : Polynomial multiplication
[2]  Chapter 30
[3]  Sections 2.5 and 2.6
Topic J : Primality testing
[2]  Section 31.8
[3]  Chapter 4
[4]  Section 7.3