Reference no: EM13536759
1.Circle T or F for each of the following statements, and briefly explain why. The better your argument, the higher your grade, but be brief. Your justification is worth more points than your true-or-false designation. Each part is 4 points.
(a) T F An inorder traversal of a Min Heap will output the values in sorted order.
(b) T F A Monte-Carlo algorithm is a randomized algorithm that always outputs the correct answer and runs in expected polynomial time.
(c) T F Two distinct degree- polynomials with integer coefficients can evaluate to thesame value in as many as d+1 distinct points.
(d) T F If a problem in NP can be solved in polynomial time, then all problems in NP can be solved in polynomial time.
(e) T F If an NP-complete problem can be solved in linear time, then all NP-complete problems can be solved in linear time.
(f) T F In a k bit binary counter (that is initialized to zero and is always non-negative), any sequence of n<2k increments followed by m<=n decrements takes O(m+n) total bit flips in the worst case, where a bit flip changes one bit in the binary counter from 0 to 1 or from 1 to 0.
(g) T F A spanning tree of a given undirected, connected graph G=(V,E)can be found in O(E) time.
(h) T F An efficient max-flow algorithm can be used to efficiently compute a maximum matching of a given bipartite graph.