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