List of required theorems

You may be asked to prove any of the theorems from the list below. In addition, several of the proofs lead to algorithms for carrying out certain procedures. Instead of being asked to prove the theorem, you may be asked to carry out the algorithm for a specific example.

From the book :

Chapter 4 : 4.2, 4.4, 4.5.1. Chapter 5 : 5.1. Chapter 12 : Proof that d_{n} = (n − 1)(d_{n−1} + d_{n−2}) and that

\frac{d_{n}}{n!} = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} .

Chapter 18 : 18.3. Chapter 8 : 8.5, 8.7.1(i), 8.7.2. Chapter 10 : 10.2, 10.4, 10.5.1, 10.5.2. Chapter 11 : 11.1, 11.4.

From the extra stuff :

Day 7 : Theorems 1,2. Day 8 : Dirac’s Theorem. Day 10 : Mantel’s Theorem. Day 15 : Either proof of König’s Theorem (up to you !).

In addition, you may be asked to implement the following algorithms :

- minimal spanning tree algorithm

- shortest path algorithm (Dijkstra)

Finally, you should be able to solve various tyes of linear recurrence relations.