Algorithms and Complexity Antoine Joux

News

16.11.2020

Timetable for the first presentations

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... 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

 

09.11.2020

Topic assignation

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... 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

 

 



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators