Algorithms and Complexity

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

 

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