Comments on Homework 11

1. Unweighted shortest path.

   The question asked to show your work by showing the contents of the queue at each iteration, the order in which vertices are removed from the queue, and a table of the dist labels as they are updated in each iteration of the while loop. Do that!

   The beginnings of a table:

   removed	queue	A	B	C	D	E	F	G	H	I	J
   	A	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
   A	BC	0	1	1	∞	∞	∞	∞	∞	∞	∞

2. Bipartite graph.

   Show a similar table for the colors assigned, which are assigned when vertices are discovered.

   Trace the algorithm even though you can observe odd-length cycles (and in particular, triangles) in the graph and know that it isn't bipartite.

   Colors are checked when a vertex is removed from the queue and its incident edges are traversed, not when they are assigned. (Assign the opposite color of the current vertex to vertices connected by discovery edges, and check the already-assigned color for non-discovery edges.)

3. DFS

   Trace the recursive version of the algorithm.