True or False, plz indicate the reasons. Indicate whether each of the following

Question

True or False, plz indicate the reasons.

Indicate whether each of the following statements is true or false. There is one mark for each correct answer and zero marks for each incorrect answer. Statement 2 2.1 n2120n2 O(n3) 3 School Integer Multiplication takes time (n2 4 The all-pairs shortest path problem is currently solvable on any graph in O(n) time. S It is known that there are problems in NP' that are not in P 6 The Boolean Satisfiability Problem is NP-Hard 7 Every problem that is NP-Hard is also known to be NP-Complete 8 | AVL trees can degenerate to a worst case ?(n) time for find operations. 9 Dijkstra's single-source shortest path algorithm cannot work on graphs containing negative-weight cycles. 10 Exponential search is useful when the length of its input list is not known.

Explanation / Answer

(Ans-)

(1) TRUE statement

(2) FALSE because it is O(n^2).

(3)TRUE Because addition is Linear time O(n) and if we do binary multiplication we would first multiply all the bits and shift it. After we finish shifting and multiplying all the bits we would do the addition. So I am guessing the recursive call of the multiplication is O(n) and the addition of the result will be O(n). So combing the two run time will give us O(n^2).

(4)FALSE since it is O(n^3) in flyod warshall algorithm.

(5)FALSE . No, this is unknown (with the exception of the trivial languages ? and ??, these two are not complete because of the definition of many-one reductions, typically these two are ignored when considering many-one reductions). Existence of an NP problem which is not complete for NP w.r.t. many-one polynomial time reductions would imply that P?NP which is not known (although widely believed). If the two classes are different then we know that there are problems in NP which are not complete for it, take any problem in P.

If the two complexity classes are different then by Ladner's theorem there are problems which are NP-intermediate, i.e. they are between P and NP-complete.

They are still polynomial time reducible to NP-complete problems so they cannot be harder than NP-complete problems.

(6)FALSE since it is NP-complete because it can be solved in a polynomial time complexity.

(7)FALSE . since every NP-complete is NP-hard.

(8)TRUE

(9)TRUE Because

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again - it assumes the path developed to this path is the shortest.

But with negative weights - it might not be true. For example:

Dijkstra from A will first develop C, and will later fail to find A->B->C

Note that this is important, because in each relaxation step, the algorithm assumes the "cost" to the "closed" nodes is indeed minimal, and thus the node that will next be selected is also minimal.

The idea of it is: If we have a vertex in open such that its cost is minimal - by adding any positive number to any vertex - the minimality will never change.
Without the constraint on positive numbers - the above assumption is not true.

(10)TRUE

Since we do "know" each vertex which was "closed" is minimal - we can safely do the relaxation step - without "looking back". If we do need to "look back" - Bellman-Ford offers a recursive-like (DP) solution of doing so.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.