Algorithms and Complexity

Algorithms and Complexity

If you have not written to me yet concerning your topic assignation, please do so as soon as possible.

 

 

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.

This proseminar will be organized in block sessions.

First session: Briefing and topic assigment, May 15th, 9:00-10:00, CISPA C0 building room 0.07

Second session: First presentations June 20th, 14:00-17:00 (CISPA C0 room 0.02) and June 27th, 9:00-12:00 (CISPA C0 room 0.07)

Organization of the second sessions: You are expected to be present at both dates, if not possible because of other constraints, please inform me in advance.

Each of you will be assigned a slot of 30 minutes. You will have between 15 and 20 minutes for your presentation, the rest of the time being for questions.

 

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.

 

Main References
[1] Arora and Barak. Computational Complexity : A Modern Approach.

[2] Introduction to Algorithms (3rd edition). Cormen, Leiderson, Rivest, Stein.

[3] Algorithms and Complexity. Wilf. 

[4] Complexity of Algorithms. Gacs and Lovasz.

[5] Lecture Notes on Computational Complexity. Trevisan.

The references are available from the library.