Final Flashcards
(51 cards)
What’s the best evidence that computer scientists have that P does not equal NP?
All NP-Complete problems can be solved if you solve one of them, but not even one of them has been solved
(T/F) If a problem is NP it must be intractable
F, A problem isn’t necessarily intractable in NP
NP
Set of all decision problems where you can check if a solution is correct in polynomial time
P
Set of all decision problems where you can find a solution in polynomial time
(T/F) log n = O(sqrt(n))
T
(T/F) A breadth-first search algorithm uses a stack
F
(T/F) A graph G = (V, E) is said to be dense if |E| is O(|V|^2)
T
(T/F) The worst-case asymptotic complexity of Dijkstra’s algorithm in a dense graph is O(|V|^2)
T
(T/F) If an undirected graph G = (V,E) has the same weight for every edge, then both the single-source shortest path problem and the minimal spanning tree problem for the graph can be solved in linear time.
T
(T/F) The shortest path between two vertices in a minimum spanning tree is always a shortest path between the two vertices in the full graph
F
(T/F) The greedy algorithm for the fractional knapsack problem takes a fractional amount of at most one item
T
(T/F) Like Dijkstra’s algorithm, Prim’s algorithm does not work correctly unless all edge weights are non-negative
F
(T/F) All dynamic programming algorithms have the same asymptotic complexity.
F
(T/F) If a depth-first traversal of a directed graph G yields no back edges,then the graph G is cyclic.
F
(T/F) Any problem that is in the complexity class P is also in thecomplexity class NP, even if P ≠ NP.
T
(T/F) The Boolean satisfiability problem can be solved by a deterministicpolynomial-time algorithm if and only if P = NP
T
(T/F) If a problem is NP-hard, it is also NP-complete
F
For a recurrence relation of the form T(n) = aT(n/b) + n d , the Master Theorem says that T(n) is bounded asymptotically as follows:
T(n) = | O(n^(d) logn if a = b^d
| O(n^d) if a < b^d
Consider the following recurrence:
T(n) = | 16T(n/4) + 5n^2 n>k
| theta(1) n <= k
where k is a small integer. Indicate which case of the Master theorem applies(first, second, or third), and solve the recurrence
O(n^logb(a)) if a>b^d
second, O(n^(2) logn)
For a recurrence relation of the form T(n) = aT(n/b) + n d , the Master Theorem says that T(n) is bounded asymptotically as follows:
T(n) = | O(n^(d) logn if a = b^d
| O(n^d) if a < b^d
Suppose that we have a divide-and-conquer algorithm for solving acomputational problem that for an input of size n, divides the problem intotwo independent subproblems of input size 2n/5 each, solves the twosubproblems recursively, and combines the solutions to the subproblems.Suppose that the time for dividing and combining is O(n). Give a recurrencerelation for the running time of this algorithm and then solve the recurrence
O(n^logb(a)) if a>b^d
third, O(n)
The binary heap data structure is very useful in implementing an efficient priorityqueue. The two key operations of a priority queue are (i) insertion of a new element,and (ii) removal of the element with the minimum (or maximum) value
When a priority queue is implemented using a binary heap data structure,what is the complexity of each of these operations?
insertion: O(log n)
removal: O(log n)
The binary heap data structure is very useful in implementing an efficient priorityqueue. The two key operations of a priority queue are (i) insertion of a new element,and (ii) removal of the element with the minimum (or maximum) value
When a priority queue is implemented as a simple unordered array, whatis the complexity of these same two operations?
insertion: O(1)
removal: O(n)
Name three algorithms we have studied this semester that use a priority queue.
Heapsort, Dijkstras, Prims
Name three decrease-and-conquer algorithms we have studied this semester.
Euclid, Binary search, Bisection, Square root, Interpolation search
Name three divide-and-conquer (but not decrease-and-conquer) algorithms we have studied this semester
Strassen, Merge sort, Quick sort, Karatsubas
