Contents 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 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