Peer Credit Assignment

1. Please list the names of the other members of your peer group for this week and the number of extra credit points you think they deserve for their participation in group work on Tuesday and Thursday combined.

2 points

The text (p. 597) analyzes Breadth-First-Search (BFS), using an aggregate analysis (what you are reading about for Tuesday’s upcoming class) to show that because the procedure scans the adjacency list of each vertex only when the vertex is dequeued, and this happens only once, the total time spent scanning adjacency lists is O(E). Along with O(V) initialization this gives O(V+E) for the total running time.

2. What would be the running time of BFS if we replace the adjacency list with an adjacency matrix and modify it at line 12 to handle this form of input? Justify your answer.

(Note: Change of representation is a common situation and I will also ask you about the implications of change of representation on the next exam.)

Depth first search and Cycles

8 points; 2 each

DFS classifies edges as tree edges, back edges, forward edges, and cross edges (see p. 609).

3. How can you modify DFS to detect back-edges? Say what code you would modify or insert, referencing CLRS line numbers.

4. How can you modify DFS to determine whether a graph has a cycle? Again, say what code you would modify or insert, referencing CLRS line numbers.

5. What is the run time of this modified cycle-detecting algorithm on Directed graphs? Assume that it exits the DFS as soon as a cycle is found. Justify your answer.

6. What is the run time of this modified cycle-detecting algorithm on Undirected graphs? Assume that it exits the DFS as soon as a cycle is found. Justify your answer.


Dan Suthers Last modified: Sat Mar 29 21:44:46 EDT 2014