Algorithm and Data Structure Analysis: Ture or False? If it\'s false, plz provid

Question

Algorithm and Data Structure Analysis: Ture or False? If it's false, plz provide 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 1 | log(n)'"e ?(n) 2 | 2.1-n2.1 + 1 500ne (n3) 4 Insertion (assuming the added pair does not already exist) for hash table (with chaining) takes O(1) time in the worst case 5 It is known that there are problems in N P that are not in P 6 The problem to decide whether a given graph contains an Eule rian cycle is NP-hard 7 BST trees always have O(log n) time for delete operations in the 8 AVL trees always have O(log n) time for delete operations in the worst case AVL tres aiways heOUgn)time for dakae the worst case The Dijkstra single-source shortest path algorithm cannot work on graphs containing negative-weight cycles 10 Building a heap given n values takes O(nlog(n)) time in the worst case.

Explanation / Answer

(1)TRUE

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

(3) TRUE

(4) THIS IS TRUE IN CASE OF AMORTIZED ANALYSIS.The problem is usually that hash tables are not always perfect, and they may use more ancillary complexity than just storage and retrieval.

E.g. if the hashing function calculates many of the positions in the same spot given the input data (hashing clashes), then the O(1) starts to creep closer to O(N).

Also the hash function itself tends to be more complex than a simple comparison. Especially if working on string keys, the function would most probably have a complexity of its own related to the string lengths.

And if the hash table is allowed to grow / shrink, you'd find that at certain insertions / removals the complexity for that particular action jumps to O(N) instead - as the entire table needs to be rearranged.

Due to these, actual time used is sometimes less with something like a binary search tree. And especially if the number of values are small, you may even find that an unsorted linear search structure produces better practical results. So though a hash table is generally O(1), the actual situation may show that a O(log N) structure can outperform it, or even in some select cases a O(N) structure could outperform all.

(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 NPNP which are not complete for it, take any problem in P.

If there is a problem that is NP (and not P) but not NP Complete, would this be a result of no existing isomorphism between instances of that problem and the NP Complete set?

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.

If this case, how would we know that the NP problem isn't 'harder' than what we currently identify as the NP Complete set?

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

(6) FALSE . because it is NP- complete. Because 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)FALSE because it is O(n).

(8)TRUE.

(9)TRUE. Thats why we have bellmann- ford algorithm for this to operate on negative weight- edge cycles.

(10)FALSE because buliding a graph takes O(n) time.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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