# Final Exam Quiz Answer

In this article i am gone to share Coursera Course Graph Search, Shortest Paths, and Data Structures Week 4 | Final Exam Quiz Answer with you..

## Graph Search, Shortest Paths, and Data Structures

Final Exam Quiz Answer

**Also Visit This Link:** Problem Set #4 Quiz Answer

## Final Exam Quiz Answer

**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).