List of required theorems and algorithms

This list will be updated from now until the end of the course. If you are asked to prove a theorem, you may also be asked to define any term which appears in the statement of the theorem. Similarly, if you are asked to apply an algorithm to do ‘X’, you may be asked to define any terms which appear in the statement ‘X’. You are expected to know how to prove the following theorems : Chapter 4 : 4.4 Chapter 6 : 6.4 Chapter 8 : 8.3, 8.5, 8.7.2 Chapter 9 : 9.3 Chapter 10 : 10.2, 10.4 Chapter 11 : 11.1 Chapter 12 : the equation d_{n} = (n − 1)(d_{n−1} + d_{n−2}). Chapter 16 : 16.8.2 Chapter 18 : 18.3 You are expected to be able to implement the following algorithms. Note that most are connected to theorems in the book, some of which appear in the above list : Chapter 8 : Greedy algorithm for vertex-coloring (8.7.1). Chapter 9 : DfS for (i) spanning tree (9.4) (ii) min. weight spanning tree (9.3). BFS for shortest path. Chapter 10 : BFS search for alternating path in matching problems (10.5).

Greedy algorithm for edge-coloring. Chapter 11 : How to find a cycle in a tournament (11.1, see above). Ford-Fulkerson algorithm (11.4). Chapter 16 : How to construct an affine (16.6) or a projective (16.7) plane.