Asymptotic function relationships. Verify the following statements by the definitions to see if they are true or false: Q(1) Dynamic programming can solve all the problems divide and conquer can solve. Q(2). In an optimal general binary search tree, the root always contains the key with the highest search probability Q(3) Greedy algorithm is always optimal. Q(4). Suppose T is the minimum spanning tree of a graph G from source vertex s. Then a path between any pair of vertices i and j in T is the shortest path between i and j in G. Q(5). The following tree is a Huffman encoding tree for characters a, b, c, d, e, f, where the label of node a:5 means the frequency of a is 5, etc. Q(6).The problem of finding the minimum spanning tree of a graph G from a source vertex s is not an NP problem, but a P problem. Q(7). Suppose language A is in class P. If the language A is polynomial reducible to a language B, then B ∈ P. Q(8) Suppose a problem L is NP-hard. If we can prove that L is polynomial-time solvable, then P = NP. Q(9) Consider a Multipush operation, which pushes k items onto the stack. If we add Multipush to the stack other than the push and pop, then the amortized cost of stack operations will still be O(1). Q(10) Let us perform a sequence of ? operations on a data structure in which the i-th operation costs ? if ? is an exact power of 2, and 1 otherwise. Then the amortized cost of each operation is O(1)
Asymptotic function relationships. Verify the following statements by the definitions to see if they are true or false:
Q(1) Dynamic programming can solve all the problems divide and conquer can solve.
Q(2). In an optimal general binary search tree, the root always contains the key with the highest search probability
Q(3) Greedy algorithm is always optimal.
Q(4). Suppose T is the minimum spanning tree of a graph G from source vertex s. Then a path between any pair of vertices i and j in T is the shortest path between i and j in G.
Q(5). The following tree is a Huffman encoding tree for characters a, b, c, d, e, f, where the label of node a:5 means the frequency of a is 5, etc.
Q(6).The problem of finding the minimum spanning tree of a graph G from a source vertex s is not an NP problem, but a P problem.
Q(7). Suppose language A is in class P. If the language A is polynomial reducible to a language B, then B ∈ P.
Q(8) Suppose a problem L is NP-hard. If we can prove that L is polynomial-time solvable, then P = NP.
Q(9) Consider a Multipush operation, which pushes k items onto the stack. If we add Multipush to the stack other than the push and pop, then the amortized cost of stack operations will still be O(1).
Q(10) Let us perform a sequence of ? operations on a data structure in which the i-th operation costs ? if ? is an exact power of 2, and 1 otherwise. Then the amortized cost of each operation is O(1)
Step by step
Solved in 4 steps
