Fall 20 Flashcards
What is the algorithm and its runtime of finding the minimum weight path between two arbitrary nodes on a weighted, directed graph
O(E log V) – Dijkstra’s algorithm
On a weighted, undirected graph, name the algorithm and its runtime for finding the minimum spanning tree of the graph
O(E log V) – Prim’s or Kruskal’s algorithm
On an unweighted, undirected graph, name the algorithm and its runtime for finding the shortest path between two arbitrary nodes on the graph
O(V+E) – BFS
On a weighted, directed graph, name the algorithm and its runtime for determining whether two nodes of the graph are connected
O(V+E) – DFS
On a weighted, directed acyclic graph, name the algorithm and its runtime for determining the minimum weight path between two arbitrary nodes in the graph
O(X+Y) – Topological sort
On a weighted, directed graph, what is the runtime of finding an augmenting path through t he graph when implementing network flow with the Edmonds-Karp algorithm
O(V+E)
T/F If G is an NP complete problem, then G may be solved in exponential time with enumeration
True – We know its exponential, but we don’t know if its polynomial
T/F if G is an NP complete problem, the G must be framed as a yes or no question, and a yes answer must be verifiable in polynomial time
True – definition of NP
Let G be an NP complete problem. if you can solve G in time O(T), then you can solve the 3-SAT problem in time O(Tp), where p is a polynomial of the input size G and 3-SAT.
True – That’s the complete part of NP complete
If G is an NP complete problem, then G may not be solved in polynomial time
False – we don’t know
If G is an NP complete problem, then you prove that G is NP-complete by taking an instance of G, mapping it to a known NP-Complete problem like 3-SAT in polynomial time, and showing that if you can solve 3-SAT in polynomial time, then you can solve G in polynomial time.
False – its the other way around
If G is an NP complete problem, then G must be framed as a yes/no question, and a no answer must be verifiable in polynomial time
False – this is from the definition of NP
You are sorting therr following string using quicksort:
l p g s v l f f f e b w l
If you use the first character as a pivot, what will the string be right before you make the first recursive call
f l g b e f f l l v s w p
If you are trying to find the minimum spanning tree, and you have a sorted list of the edges, which algorithm should you use to find the minimum spanning tree
Kruskal’s algorithm.
Describe the process for topological sort
Maintain a list of nodes with no incoming edges.
Until the list is empty, remove a node from the list and append it to the topological sorting. For each edge coming out of the node, remove the edge from the graph; if that edge was to a node that now has no more incoming edges, put that node in the list.
Repeat until the list is empty.
