assignment 2

Assignment 2 due by the end of class Wednesday January 24 2001.

for the following graph
- draw the bfs tree, starting from vertex 1 (and show nontree edges as dashed lines)
- draw the dfs tree, starting from vertex 1 (and show back edges as dashed lines)
- list the blocks (biconnected components) in the order which they would be found by the algorithm from the notes (list each block by listing its edges in the order in which they would be popped off the stack; circle the back edges)
```
1:  5 6 12
2:  4 8 9 11
3:  9 11
4:  2 8
5:  1 6
6:  1 5 12
7:  12 13 
8:  2 4
9:  2 3 12
10: 12
11: 2 3
12: 1 6 7 9 10
13: 7
```
by modifying breadth first search, design an algorithm which takes a connected graph as input, and returns either a 2-colouring of the vertices, or an odd cycle [hint: 2-colour until you finish or get stuck], and
- prove that the algorithm is correct (namely, always returns a 2-colouring or an odd cycle, and never returns both)
- give a detailed analysis of the complexity of your algorithm
repeat the previous question by modifying a recursive version of depth first search