Algorithms Supervision 3

Recommended reading

Chapters 6, 10, 11, 12, 13, 18 of Introduction to Algorithms (3rd edition) by Cormen, Leiserson, Rivest & Stein.

Exercises

Bolded items are taken from the exercise sheet:

1. Exercise 36
2. 2009 Paper 1 Question 5, parts a), b) and c) only
3. 2007 Paper 11 Question 9
4. 2008 Paper 10 Question 9, parts a) and b) only
5. Exercise 48 (the "exercise above" is exercise 47)
6. Define the following graph terms in one sentence each:
   1. Path
   2. Connected
   3. Cycle
   4. DAG
   5. Tree
   6. Bipartite
   7. Diameter
7. Which auxiliary data structures are required when searching a graph in the following ways?
   1. Breadth-first
   2. Depth-first