Vorlesungen Einführung in die theoretische Informatik Diskrete Wahrscheinlichkeitstheorie Grundlagen: Algorithmen und Datenstrukturen Effiziente Algorithmen und Datenstrukturen II Online- und Approximationsalgorithmen Komplexitätstheorie Proseminar Graph Drawing Seminar / Masterseminar Approximationsalgorithmen Energieeffiziente Algorithmen Praktikum Algorithmen für Programmierwettbewerbe Lehrveranstaltungen für Doktoranden Oberseminar

Exercises to Complexity Theory

Announcements:

• Problem Set 0 will be presented in the first tutorial on April 10th, it is not meant to be submitted. Problem Sets with submissions start on April 14th.

General information:

• Teaching Assistant:
  Chris Pinkau
• Time and place:
  Thu, 12:30–14:00, Room 03.11.018
• Office hours:
  Tue, 13:00–14:00, Raum 03.09.057

Problem sets and solutions

• Problem set 0 – Solutions to Problem set 0
• Problem set 1 – Solutions to Problem set 1
• Problem set 2 – Solutions to Problem set 2
• Problem set 3 – Solutions to Problem set 3
• Problem set 4 – Solutions to Problem set 4
• Problem set 5 – Solutions to Problem set 5
• Problem set 6 – Solutions to Problem set 6
• Problem set 7 – Solutions to Problem set 7
• Problem set 8 – Solutions to Problem set 8
• Problem set 9 – Solutions to Problem set 9
• Problem set 10 – Solutions to Problem set 10
• Exam solutions

Other:

• The proof of the Baker, Gill, Solovay Theorem as a student/exam story
• Big picture: Overview of the known complexity classes (subject to change)
• Overview of the known reductions
• Google's doodle in honor of Alan Turing
•  
• Theoretical Computer Science Cheat Sheet
• The On-Line Encyclopedia of Integer Sequences
• History of Mathematics