True or False. plz show the resons. (a) Indicate whether each of the following s

Question

True or False. plz show the resons.

(a) Indicate whether each of the following statements is true or false There is one mark for each correct answer and zero marks for each ncorrect answer Statement 3 The Floyd-Warshall all shortest path algorithm takes time e(nm+ n2 log n). (where m is the number of edges and n is the number of nodes in the graph). 4 Kruskal's algorithm for minimum spaning tree takes time (m logm) 5 It is known that there are problems in P that are not in NP 6 The problem to decide whether a given graph contains an Eule- rian cycle is NP-harod 7 All optimisation problems are in NP 8 | AVL trees have O(log n) time for delete operations 9The Dijkstra single-source shortest path algorithm cannot work on graphs containing negative-weight cycles 10 Unbounded arrays always have O(1) time access regardless of how we decide to reallocate space for them - as long as we al ways allocate sufficient space of course.

Explanation / Answer

(Ans-)

(1)TRUE

(2)FALSE because it is (On^2).

(3)FALSE. because flyod warshall algorithm takes O(n^3) time complexity.

(4)TRUE . It takes time O(mlogm) time.

(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.

(6)FALSE . BECAUSE The problem seems similar to Hamiltonian Path which is NP complete problem for a general graph. Fortunately, we can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.

(7)TRUE

(8)TRUE

(9)TRUE BECAUSE

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.

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.

(10)TRUE

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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