### Submitting:

- All homeworks should be turned in electronically to
**myCourses**. - Paper submissions may be
**scanned**in if legible. - If you take a
**photo**of your paper solution, please take the photo outside or close to a bright**window**, for legibility.

### Due dates:

- Homeworks are due by
**10pm**on the due date (Thu). **No late**submissions are accepted.- If there are
**extenuating circumstances**, contact the instructor as soon as possible to make arrangements.

### References:

- If you find a resource helpful (from
**internet search**, blog post, Stack Overflow, online courses, our lecture notes, etc), be sure to**cite**it. Citation format doesn’t matter, but make it easy for the TA to**find**the source: e.g., a clickable link. - Code / pseudocode should be your
**own work**. If you find code online,**understand**how it works, then go write up your solution on your**own**. - The basic
**machine model**was discussed in Lecture 1. Don’t use**library**functions which obviate the bulk of a question. E.g., if you’re asked to implement a sort, don’t use Python’s`sorted()`

.

### HW8 (20pts) (solutions)

Consider the directed graph with the following **adjacency list**:

`{1:[2, 3], 2:[1, 7], 3:[2], 4:[7, 8], 5:[2, 4, 6], 6:[5, 8], 8:[3, 4]}`

In the following, any iterations over the vertex list or over the neighbours of a vertex should be done in order of vertex index.

*(1 pt)*Show the corresponding**adjacency matrix**.*(2 pts)***Draw**the graph.*(3 pts)*Demonstrate a**breadth-first search**starting at 8.*(3 pts)*Demonstrate a**depth-first search**on the graph. Show as much work as you can, including discovery/finish times.*(1 pt)*Draw the**DFS forest**and the remaining edges.**Classify**all edges in the graph.*(1 pt)*Show a**topological sort**of the graph from your DFS.*(3 pts)*Demonstrate finding the**strongly-connected components**of the graph, and draw a*component graph*.- One graph problem we touched on in class but didn’t dive into
is
**bipartite checking**. An undirected graph is*bipartite*if it is colourable using two colours (e.g., red and blue) such that no edge connects vertices of the same colour.

More precisely, `V = V_r uu V_b`, with `V_r nn V_b = O/` and `u, v in V_r => (u,v) !in E` and `u,v in V_b => (u,v) !in E`.- (a)
*(5 pts)*Design (i.e.,**pseudocode**) an algorithm to test if a graph is bipartite (return a boolean). Use a BFS strategy. - (b)
*(1 pt)*What is the**complexity**of your algorithm, assuming adjacency list representation? - (c)
*(2 pts extra credit)*Design a DFS bipartite checker.

- (a)