Lectures: Lecture 1-2 (Basics) Lecture 3 Lecture 4 Lecture 5 Exercise Sheets: Exercise Sheet 3 Exercise Sheet 4 Exercise Sheet 5 Contents: Problem Instance Types: Decision Problem Search Problem Decision Problem Optimisation Problem Complexity Class P NP Nondeterministic Turing Machine NP-hard Decision Problem NP-complete Decision Problem Landau Symbols Big-O Notation Big-Theta Notation Big-Omega Notation Small-O Notation Running Time Polynomial Running Time Quasipolynomial Running Time Decision Problems Independent Set Problem Independent Set Vertex Cover Problem Vertex Cover Clique Decision Problem Clique Dominating Set Problem Dominating Set Encoding Binary Encoding Unary Encoding Encoding Matters Weakly NP-hard Decision Problem Strongly NP-hard Decision Problem SAT Formulas Krom Formula Horn Formula Tree-like Formula Conflict-Driven Clause Learning Dynamic Programming OLD: Approximation Algorithm Scheduling Problem Scheduling Notation Release Time Processing Time Due Date Strict Deadline Preemption Precedence Constraint Completion Time Unit Penalty Lateness Makespan Total Completion Time Average Completion Time Schedule Feasible Schedule Interval Scheduling Problem Earliest Due Date First Algorithm (Interval Scheduling) Interval Partitioning Problem Depth Earliest Start Time First Algorithm Graham’s List Scheduling Algorithm A Deadline Gap Can Hide Subset Sum Two Machines Can Hide Partition Fixed Machines Hide Number Partitioning k-Partition Problem 2-Partition Problem 3-Partition Problem Sub-exponential algorithms Landau Symbols Big-O Notation Big-O-Star Notation Small-O Notation Big-Theta Notation Big-Omega Notation Small-Omega Notation Asymptotic Dominance Single-exponential Time Algorithm Big-O-Star Notation 3-SAT Exponential Time Hypothesis Russell Impagliazzo Ramamohan Paturi Francis Zane Strong Exponential Time Hypothesis Subexponential Time Needs a Ruler 3-Colouring Problem 4-Colouring Problem Planar Graph Plane Plane Drawing Fáry’s Theorem Planar Vertex Cover Problem Planar Independent Set Problem Planar Dominating Set Problem Matroid Axioms Non-emptiness Heredity Exchangeability Examples Vector Matroid Graphic Matroid Uniform Matroid Partition Matroid Basis Family Intersection Rank Rank Function Circuit Span Exchange Graph COMSOC Alternatives Voters Preference profiles Plurality Plurality with Runoff Single Transferable Vote Borda Count Borda Score Borda Winner Condorcet Condorcet Paradox Condorcet-consistent Voting Rule Lull’s Rule Dodgson’s Rule Young’s Rule Kendall-Tau Distance Kemeny’s Rule Majority Graph Weighted Majority Graph Exercise Sheets Exercise Sheet 3 Exercise Sheet 4 Exercise Sheet 5