Algorithms Supervision 4

Recommended reading

Chapters 17, 19, 20, 21 of Introduction to Algorithms (3rd edition) by Cormen, Leiserson, Rivest & Stein.

Exercises

1. 2006 Paper 5 Question 1
2. Briefly describe what the Bellman-Ford algorithm does, and how it does it. What is the purpose of the post-processing phase at the end? What is the overall complexity of the algorithm?
3. 2008 Paper 4 Question 2, parts b) and d) only
4. 2014 Paper 1 Question 10, part a) only
5. Question 11 from the exercise sheet
6. Question 18 from the exercise sheet