Exam

Form

The exam will be an oral exam with no preparation time. There is allocated 30 minutes per student, including time for evaluation. The question for the exam is determined by a randomized process.

Dates

The dates for examination are Friday January 21 and Friday January 28.

If needed it may be possible to take the exam on a different date after agreement by the examiners.

Exam Questions

  1. Time and Space complexity. Alternation and the Polynomial time Hierarchy.
    (Lectures 1,2,3,4,5,6,7)
  2. Randomized Computation and Counting Complexity.
    (Lectures 8,9,10,11,12(first part))
  3. Boolean Circuits, Constructions and Lower Bounds.
    (Lectures 12(last part),13,14,15,16)
  4. Interactive proofs, Probabilistically Checkable Proofs and Inapproximability.
    (Lectures 17,18,24,25,26,27)
  5. Expanders graphs and Derandomization.
    (Lectures 19,20,21,22,23)
The questions are very broad, so it is expected that you focus on one particular part within the exam question chosen. After your presentation of this part, we will ask more broadly within the curriculum. You will be expected to demonstrate both detail knowledge and overview knowledge of the contents of the course. See also the section Learning outcomes and competences in the official course describtion: English / Danish

Schedule

The exams will be held in Turing-014.

Friday January 21

This day the exam is held together with the exam in Computational game theory, Q2, 2010. The exam starts 9:00. Times below are approximate.
  1. 09:00 CGT
  2. 09:30 20042199 Andreas Hummelshøj Jakobsen
  3. 10:00 CGT
  4. 10:30 20071707 Camilla Lodahl Gravgaard

Friday January 28

The exam starts 9:00. Times below are approximate.
  1. 09:00 20063074 Claes Højer Jensen
  2. 09:30 20071268 Jesper Broni Andersen
  3. 10:00 20100140 Søren Valentin Haagerup