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 Covid-19 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.infomath-bib.de/tmp/vorlesungen/info-advanced_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