Test 2 Questions Flashcards
A graph G = (V, E) is sparse if
E = V
For a priority queue implemented as a binary heap, the two operations of inserting and removing an element (and maintaining the heap property) each have ____ complexity, where n is the size of the priority queue.
O(log n)
Prim’s algorithm can find a minimal spanning tree of a graph only ___.
If the graph is undirected.
T/F
There is an algorithm that tests whether a graph is acyclic in worst-case complexity O(V+E)
TRUE
DFS
Breadth-First Search uses a
QUEUE
T/F
An optimal solution to the fractional knapsack problem can be found by a greedy algorithm, whereas an optimal solution to the 0/1 knapsack problem cannot
TRUE
In an undirected graph with unit edge costs, a shortest path tree is always ___.
a shortest path between the two vertices in the full graph.
Bellman-Ford solves ___
The single-source shortest path problem with negative weight edges but no negative weight cycles.
Time Complexity of Bellman-Ford :
Θ(V * E)
The single source shortest path in an acyclic graph can be solved in ___ time, even if the graph has negative cost weight.
Θ(V + E)
T/F
The single-source-longest path problem in a graph is just as easy to solve as the single-source shortest path problem in the same graph.
FALSE
Describe one important similarity and difference between “Divide and Conquer” and Dynamic Programming
Similarity: Both recursively divide the problem into subproblems and solve those subproblems.
D/C solves each subproblem and never visits that subproblem again.
DP, the subproblem may overlap, so the subproblem’s results are stored in a table for later use.
What is the asymptotic time complexity of topological sort?
O(V+E)
Is it possible to perform a topological sort of an undirected graph? Explain why.
No.
Undirect graphs may produce cycles which is not allowed in topological sort.
Also, you need direction/order for top sort.
T/F
Prim’s and Dijkstra’s have the same time complexity.
TRUE
What is Prim’s and Dijkstra’s time complexity when they are used to solve a problem in a dense graph, and the priority queue is implemented as an UNSORTED ARRAY
O(V^2)
Describe at least 2 properties that are characteristic of any dynamic programming algorithm.
- Has recurrance relationship.
- Has table, each entry the distance we are optimizing and a pointer.
- Traceback property with pointers.
Most efficient algorithm for solving Single-Source shortest path problem in an unweighted sparse graph.
Breadth First Search
O(V+E)
Most efficient algorithm for single-source shortest path problem in a graph with non-negative edge weights
Dijkistra’s
O(V log V) or
O(E log V) if E = V
Most efficient algorithm for single source shortest path in a graph with negative weights but no negative weight cycles
Bellman Ford
O(V*E) or
O(V^2) if E = V
What is meant by a strongly connected component of a directed graph?
That every vertices in the subgraph can access any other vertice in that same subgraph.
What is the asymptotic complexity of the best algorithm for finding the strongly connected components of a directed graph?
DPS
O(V+E)
