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 Exercise Sheets Exercise Sheet 3