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. (1 pt) Show the corresponding adjacency matrix.
  2. (2 pts) Draw the graph.
  3. (3 pts) Demonstrate a breadth-first search starting at 8.
  4. (3 pts) Demonstrate a depth-first search on the graph. Show as much work as you can, including discovery/finish times.
  5. (1 pt) Draw the DFS forest and the remaining edges. Classify all edges in the graph.
  6. (1 pt) Show a topological sort of the graph from your DFS.
  7. (3 pts) Demonstrate finding the strongly-connected components of the graph, and draw a component graph.
  8. 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.