Exam

This page collects information on the oral exam on January 29th.

Basic information

• The oral exam takes at most 25 minutes.
• Thore Husfeldt will be present as the additional external examiner.
• There are no aids apart from the ones mentioned below in the topics. You will be able to draw on a blackboard/whiteboard
• First half: You will draw randomly a topics from the topics below. In around 6-8 minutes you briefly summarize the topic (see details below). Then you will be asked a few questions about it.
• Second half: The examiners will change to a second topic and ask you a few questions about this.
• Specific questions regarding your project may also be asked in the second part, possibly in the context of the topic.

Topics

The following list will be extended until the last lecture of the course (estimated at December 10th)

• Preprocessing
  • Important: you know the basic definitions, the Sunflower Lemma, and you can give and explain examples of Kernelization algorithms and how they are analyzed
  • Less important: exactly reciting every rule for every problems (as long as you can give some examples)
• Branching
  • Important: be able to describe on a high level the functioning of branching algorithms (and Branch-and-Bound), be able to give examples of branching algorithms and how they are analyzed, be able to explain Branch-and-Bound for ILPs
  • Less important: exactly reciting every detail for every problems (as long as you can give some examples)
• FPT via Linear Programming
  • Important: be able to explain basic ideas for Vertex Cover via LP relaxation, Eisenbrand-Weismantel algorithm, proximity and high level ideas of proof (including Steinitz Lemma)
  • Less important: knowing by heart every detail of the proofs (as long as you can explain the high level intuition); other FPT results for ILP (Lenstra’s algorithm, block structures)
  • Aids: In case you are asked to explain the Eisenbrand-Weismantel algorithm, you will be given the corresponding lecture slide
• Complexity Theory
  • Important: you know the basic definitions (ETH, parameterized reductions), can explain the basic structure of the proof of the Sparsification Lemma, explain typical approach for proving hardness of parameterized problems and give examples
  • Less important: reciting calculations in the Sparsification Lemma, knowing every reduction by heart
  • Aids: In case you are asked to explain the Sparsification Lemma, you will be given the lecture slide with the branching algorithm
• Treewidth
  • Important: you know the basic definitions (path decomposition, tree decomposition), are able to construct a path/tree decomposition for a given graph, can explain (on a high level) how to apply dynamic programming on path/tree decompositions, you know Courcelle’s Theorem, you can model problems in monadic second order logic
  • Less important: reciting details of the proof of recurrences
• Randomized Algorithms
  • Important: you know the basic definitions (Monte-Carlo Algorithm), are able to relate success probability to running time, understand how Color-Coding can be used to simplify parameterized problems, can explain on a high level why walk-SAT is faster than naive enumeration
  • Less important: reciting technical calculations in the k-SAT algorithm
• Fine-Grained Complexity
  • Important: you understand how prove conditional running time lower bounds can be proven for polynomial time solvable problems. You know the definition of SETH and can give examples of consequences and how they are obtained on a high level
  • Less important: The results derived from SETH that we did not prove

Summary of randomly drawn topic

• You will briefly (6-8 minutes) explain a randomly drawn topic. You can use the blackboard/whiteboard
• You do not have to prepare a polished speech. Talk naturally
• Focus on high level (relevance of the topic in the context of the course, basic ideas)
• Be concise and keep what you write on blackboard/whiteboard short