# Graph Search, Shortest Paths, and Data Structures Week 4 Final Exam Quiz Answer

## Graph Search, Shortest Paths, and Data Structures Week 4 Final Exam Quiz Answer

#### Final Exam

Question 1)

Consider a directed graph G = (V, E) with non-negative edge lengths and two distinct vertices s and t of V. Let P denote a shortest path from s tot in G. If we add 10 to the length of every edge in the graph, then: (Check all that apply.]

- P definitely remains a shortest s – t path.
- If P has only one edge, then P definitely remains a shortest s – t path.
- P definitely does not remain a shortest s – t path.
- P might or might not remain a shortest s – t path (depending on the graph).

Question 2)

What is the running time of depth-first search, as a function of n and m, if the input graph G = (V, E) is represented by an adjacency matrix (i.e., NOT an adjacency list), where as usual n = |V| and m = |E|?

- θ(n2 log m)
- θ(n + m)
- θ(n2)
- (n ✱ m)

Question 3)

What is the asymptotic running time of the Insert and Extract-Min operations, respectively, for a heap with n objects?

- ⊝(n) and ⊝(1)
- ⊝(log n) and ⊝(log n)
- ⊝(log n) and ⊝(1)
- ⊝(1) and ⊝(log n)

Question 4)

On adding one extra edge to a directed graph G, the number of strongly connected components…?

- …cannot decrease
- …might or might not remain the same (depending on the graph).
- …cannot decrease by more than 1
- …cannot change

Question 5)

Which of the following statements hold? (As usual n and m denote the number of vertices and edges, respectively, of a graph.) (Check all that apply.]

- Depth-first search can be used to compute the strongly connected components of a directed graph in O(m + n) time.

- Depth-first search can be used to compute a topological ordering of a directed acyclic graph in O(m+n) time.

- Breadth-first search can be used to compute the connected components of an undirected graph in O(m +n) time.

- Breadth-first search can be used to compute shortest paths in O(m + n) time (when every edge has unit length).

Question 6)

When does a directed graph have a unique topological ordering?

- Whenever it has a unique cycle
- None of the other options
- Whenever it is directed acyclic
- Whenever it is a complete directed graph

Question 7)

Suppose you implement the operations Insert and Extract-Min using a sorted array (from biggest to smallest). What is the worst-case running time of Insert and Extract-Min, respectively? (Assume that you have a large enough array to accommodate the Insertions that you face.)

- ⊝(n) and ⊝(n)
- ⊝(1) and ⊝(n)
- ⊝(n) and ⊝(1)
- ⊝(log n) and ⊝(log n)

Question 8)

Which of the following patterns in a computer program suggests that a heap data structure could provide a significant speed-up (check all that apply)?

- Repeated maximum computations
- Repeated lookups
- Repeated minimum computations
- None of the other options

Question 9)

Which of the following patterns in a computer program suggests that a hash table could provide a significant speed-up (check all that apply)?

- Repeated minimum computations
- Repeated maximum computations
- Repeated lookups
- None of the other options

Question 10)

Which of the following statements about Dijkstra’s shortest-path algorithm are true for input graphs that might have some negative edge lengths? Check all that apply.]

- It may or may not correctly compute shortest-path distances (from a given source vertex to all other vertices), depending on the graph.

- It is guaranteed to terminate.

- It is guaranteed to correctly compute shortest-path distances (from a given source vertex to all other vertices).

- It may or may not terminate (depending on the graph).