Coursera Answers

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


Graph Search, Shortest Paths, and Data Structures Week 4 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..




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